Cant understand Quick Select Algorithm

Question

I am having a problem understanding the Quick select algorithm. I know it is based on the Quick sort algorithm (which I am familiar with) and that it gives you the required result perhaps leaving a portion of the array unsorted.Now here is where I am having difficulty. The question is find the 2nd smallest element from the array which is:

int a[4] = {1,3,5,2} ;

Now suppose we are selecting pivot randomly then according to this post we have the following conditions:

k == pivot. Then you have already found kth smallest. This is because the way partition is working. There are exactly k - 1 elements that are smaller than the kth element.
k < pivot. Then kth smallest is on the left side of pivot.
k > pivot. Then kth smallest is on the right side of pivot. And to find it you actually have to find k-pivot smallest number on right.

I would appreciate it if someone could explain how k==pivot means that we have found the kth (in my case the 2nd smallest element). Also if its k < pivot do we repeat the process for the left side of the pivot ?

score 2 · Answer 1 · answered Mar 16 '14 at 07:14

If k = pivot you'll have k-1 items to the left of pivot. Thanks to the partitioning each of these is less than the pivot item. Also, thanks to partitioning, each of the items to the right is greater than the pivot item. Therefore the pivot item must be the kth greatest. Makes sense?

score 1 · Accepted Answer · answered Mar 16 '14 at 07:13

Yes , when pivok == k , you have k-1 elements in left of the pivot which are smaller than pivot , so you have found the k-th smallest number of the array i.e. the pivot , but if k < pivot , do search in left side of array because pivot > kth smallest element , otherwise pivot < kth smallest element of array so search in right side to increase pivot .
from wikipedia :

// Returns the n-th smallest element of list within left..right inclusive (i.e. n is zero-based).
  function select(list, left, right, n)
     if left = right        // If the list contains only one element
         return list[left]  // Return that element
     pivotIndex  := ...     // select a pivotIndex between left and right, e.g. left + Math.floor(Math.random() * (right - left + 1))
     pivotIndex  := partition(list, left, right, pivotIndex)
     // The pivot is in its final sorted position
     if n = pivotIndex
         return list[n]
     else if n < pivotIndex
         return select(list, left, pivotIndex - 1, n)
     else
         return select(list, pivotIndex + 1, right, n)

Hope this helps !

Cant understand Quick Select Algorithm

2 Answers2