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 ?

Answer 1

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 !