Yuhang He's Blog

Some birds are not meant to be caged, their feathers are just too bright.

Quick sort algorithm

Quick sort algorithm is very popular. The basic idea behind it is that: given an array of real-valued numbers, instead of sorting it directly, we randomly select a sentinel number from it and further set those number who are smaller than it on its left side, while the number that are larger than it on its right side. Then, the array is divided into two parts by this sentinel number. The same process applies to these two parts individually so that more numbers are correctly sorted. The quick sort is finished when no more numbers need to be sorted.

When it comes to implementation, we should set two sentinel indexes left, right to monitor whether the left-right side division is finished. In most cases, the sentinel number base is set to the first value of the array. left moves from left to right to find the number that is larger than base, right moves from right to left to find the number that is smaller than base. Whenever it finds the appropriate number, we move it to the previous found location.

The core code looks like:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int Division( int a[], int left, int right )
{
  int base = a[left];
  while( left < right )
  {
    while( left < right && a[right] > base )
      --right;
    a[left] = a[right];
    while( left < right && a[left] < base )
      ++left;
    a[right] = a[left];
  }
  a[left] = base;
  return left;
}

The overall recursion code is:

1
2
3
4
5
6
7
8
9
10
11
void QuickSort( int a[], int left, int right )
{
  int i = 0;
  int j = 0;
  if( left < right )
  {
    i = Division( a, left, right );
    QuickSort( a, left, i - 1 );
    QuickSort( a, i+1, right );
  }
}