Qsort

qsort

Quick sort is a sorting algorithm with typical of O(nlogn) complexity.

The steps are:

1. Pick an element, called a pivot, from the list.
2. Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it. 
3. Recursively apply the above steps to the sub-list of elements with smaller values and separately the sub-list of elements with greater values.

pivot choice:

- selecting left most  item of array as pivot may not be a good choice specially if array is already sorted.

- random index or middle index are probably better choices

- middle index defined as (left+right)/2 may cause integer overflow if boundary indexes are very large values. Instead better use left + (right-left)/2. 

C code snippet:

void qsort (int v[], int left, int right) {
  int i, last;
  if(left >= right)
    return;
  swap(v, left, (left + right)/2);
  last = left;
  for(i= left+1; i <= right; i++) 
    if(v[i] < v[left])
      swap(v, ++last, i);
  
  swap(v,left,last);
  qsort(v, left, last-1);
  qsort(v, last+1,right);

 }

void swap(int v[], int i, int j){
   int tmp;
   tmp = v[i];
   v[i] = v[j];
   v[j] = tmp;
}