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
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
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
The overall recursion code is:
1 2 3 4 5 6 7 8 9 10 11