(Java) Problem 12.9

**daemoohn** · February 25, 2016, 9:41am

Hi,

I took a look at the partitioning function description. While this quickselect problem probably needs to sort items decreasingly in order for the pivot of the kth largest element to be at position k-1, the description (at least, but maybe the code too) of the partitioning function is the one of the quicksort problem.
In quicksort you are interested to separate items smaller than the pivot to the left of the pivot and the items larger than the pivot to the right of the pivot. Consequently, this partitioning would solve the problem of the kth smallest item.

Please correct me if I’m in error.

**damluar** · March 17, 2016, 11:41am

Hi,

it is easy to compute kth smallest/largest element if array is sorted, right? But sorting requires O(n * logn) and we don’t need all elements sorted, it is more than we need.

So someone smart decided to use modified version of quick sort called quick select. It is almost exactly the same code as quick sort, but we recurse only on one half of the array.

So the idea is to partition around the pivot (as we do in quick sort) and look where the pivot index is. If pivotIndex < k - 1 than we know that our element is to the right of the pivot and we recurse there. Otherwise we go to the left part.

So quick select also sorts the array, but only partially and until we find the kth element. Since we recurse only on one half, the average running time is O(n).

**daemoohn** · March 17, 2016, 11:43am

Yeah, I know that, I knew of quickselect before solving the problem. The issue that I think I found is that we would be interested in sorting them in reverse order, not the order described in the solution.

**damluar** · March 17, 2016, 11:50am

the description (at least, but maybe the code too) of the partitioning function is the one of the quicksort problem.

since quick sort and quick select share exactly the same partition function, it is ok that description is the same.

Could you clarify exactly which statement is wrong in your opinion?

**daemoohn** · March 17, 2016, 12:01pm

If you want to find the kth largest item, you want to partially sort the items in decreasing order, right?
Normal, quicksort sorts the item in increasing order.

Here is the mismatch.

**damluar** · March 17, 2016, 12:02pm

Right, but quick sort can also be used to sort elements in reversed order.

**daemoohn** · March 17, 2016, 12:05pm

Yes, it is correct. From what I remember, the description of the partitioning function talked about sorting in normal order the items. This does not apply for this particular problem.

**tsunghsienlee** · September 6, 2016, 1:24am

I think there is a misunderstanding here as we actually partition the array by using a Compartor object, and in this problem, we use greater than. So it will solve the problem as we want and there is no reason to use sorting. You might want to check the code again.