Partial Sort

[DreamTime]

I am looking up some variations of quick sort. Right now, I want to write a program that partially quick sorts a list of integers so that it only sorts the highest 10 integers in the list. What are some ways I can do this?

[Semoirethe]

I would just do 10 iterations of selection sort. Quick sort, and divide and conquer sorts in general, are not good for partial sorting of arrays as they must divide it up and do work the entire array piece by piece with the intermediate steps not being all that useful by themselves. Selection sort however is perfect for this type of thing.

[DreamTime]

I understand this, but I am learning variations of different sorting algorithms in my class right now. Right now, I need to learn partial quick sort, but I was not given any examples. Unfortunately, I learn best by seeing examples or at least seeing similar related things. I can't come up with it on my own, although I could easily put together a basic quick sort algorithm.

[Semoirethe]

Okay, well for partial quicksort just do a normal quicksort until you place your pivot in the kth position from the end(end-10 in this case) and then stop recursing on the 'lower' half if you're pivot isn't in the k range.


so

void partial_quick_sort (...) {
    int pivot = blah
    int part = partition(...)
    partial_quick_sort(array, part+1, end)
    if(part > end-k) partial_quick_sort(array, beg, part-1)

That, with possibly a little modification, should work.