Little bit about quick sort/ quick select

Quick Sort algorithm

This algorithm is one of the efficient and popular sorting algorithms you may encounter in your programming, it majorly includes two parts:

1) First it applies partition function to divide a array  into two sub-arrays;  
2) Then apply itself recursively on these two sub-arrays separately;

The essence of this algorithm is to implement a partition function, which uses two indices to divide a array into right-left sub-arrays, separated by an arbitrary element from the array called pivot element, all elements in the left sub-array are less than the pivot while all elements in the right sub-arrary are bigger than the pivot. 

[code]

int partition(vector<int> &s, int start, int end)
{
      int pivot = s[end];   // could be any element from s
      int pindex = start;
      for( int i = start; i< end; i++) {
          if (s[i] <= pivot) {
              swap(s[pindex], s[i]);
              pindex ++;
          }
      }
      swap(s[pindex], s[end]); 
      return pindex;
}


void quicksort(vector<int> &s, int start, int end)
{
    if (start >= end) return;
    int pindex = partition(s, start, end);
    quicksort(s, start, pindex - 1);
    quicksort(s, pindex + 1 , end);
}

Quick Select algorithm

With the same partition function, we can implement a quick select algorithm.

For example, find the kth smallest item in the array:

[code]

void quickselect(vector<int> &s, int start, int end, int k)
{
    int pindex = partition(s, start, end);
    if (k < pivot) return quickselect(s, first, pivot-1, k);
    if (k > pivot) return quickselect(s, pivot+1, end, k);
    if (k == pivot) return s[pivot];
}

3-way partitioning 

(Dijkstra 3-way partitioning)

The above partitioning are 2-way partitioning, it partition array into 2 parts (or sub-arrays) as we analyzed. Let's find out if we can partition an array into 3 parts so that:
1) left part: the elements less than pivot;
2) middle part: the elements equal to pivot;
3) right part: the elements bigger than pivot; 

(By the way, this can help to solve Dutch national flag problem)

[code]

void threewaypartitions(vector<int> &s, int start, int end, int ke)
{
    int pivot = ke;
    int lt = start, gt = end;
    int i = lt;
    for(;i<=gt;) {
       if(s[i] < pivot)      swap(s[i++], s[lt++]);
       else if (s[i] > pivot) swap(s[i], s[gt--]);
       else i++;
    }
}