Java Projects - Second Edition

Quicksort

Sir Charles Antony Richard Hoare developed the quicksort algorithm in 1959. It is a typical divide-and-conquer algorithm. Here is how it goes.

To sort a long array, pick an element from the array that will be the so-called 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 we start partitioning, we do not know how long the left side will be and where the right side will start. The precise way we work this out will be explained very shortly. For now, it is important that we will have an array divided so that the elements from the start of the array to a certain ...