Quick sort

Sir Charles Antony Richard Hoare developed the quick sort algorithm in 1959. It is a typical pide and conquer algorithm. To sort a long array, pick an element from the array that will be the pivot element. Then, partition the array so that the left side will contain all the elements that are smaller than the pivot and the right side will contain all the elements that are larger than, or equal to the pivot. When this is done, the left side and the right side of the array can be sorted by calling the sort recursively. To stop the recursion, when we have one single element in the array, we will declare it sorted.

We talk about a recursive algorithm when the algorithm is defined partially using itself. The most famous recursive definition is the Fibonacci series that is 0 and 1 for the first two elements and any later element the n^th element is the sum of the (n-1)^th and the (n-2)^th element. Recursive algorithms are many times implemented in modern programming languages implementing a method that does some calculation but sometimes calls itself. When designing recursive algorithms, it is of utmost importance to have something that stops the recursive calls; otherwise, recursive implementation will allocate all memory available for the program stack and stop the program with error.

The partitioning algorithm goes the following way: we will start to read the array using two indices from the start and end. We will first start with the index that is small and increase the index until it is smaller than the large index, or until we find an element that is greater than or equal to the pivot. After this, we will start to decrease the larger index so long as it is greater than the small index and the element indexed is greater than or equal to the pivot. When we stop, we swap the two elements pointed by the two indices, if the indices are not the same, and we will start increasing and decreasing the small and large indices, respectively. If the indices are the same, then we are finished with the partitioning. The left side of the array is from the start to the index where the indices met minus one; the right side starts with the index and lasts until the end of the to-be-sorted array.

This algorithm is usually O(n log n), but in some cases it can degrade to be O(n²), depending on how the pivot is chosen. There are different approaches for the selection of the pivot. In this book, we will use the simplest: we will select the first element of the sortable collection as a pivot.