The quicksort is an example of a divide and conquer algorithm in that it divides the sorting problem into smaller problems by dividing the list of items to be sorted into smaller subsets.
The pivot is the mechanism that is used to segment the list.
Requirements:
Describe how the quicksort works.
Including a discussion of the pivot, how it is selected, and why the pivot is important to the quicksort.
According to (Shaffer, 2011), the Quick Sort is the fastest known sorting algorithm in practice.
Quick Sort is a general-purpose, in-memory, space efficient internal sorting algorithm that uses the divide and conquer strategy (Shaffer, 2011).
It starts by selecting an element as the pivot and fix it in its position, then sorts the array by moving elements smaller than the pivot to the left subarray and elements larger than the pivot to the right subarray.
It then recursively sorts the subarray to the left of the pivot and the subarray to the right of the pivot, until the entire array is sorted.
Selecting the right pivot is crucial to the performance of the Quick Sort algorithm.
The pivot, by definition, is an element that divides an the array elements into two halves, one is smaller than the pivot and the other is larger than the pivot.
That is, the best pivot is the median of the array elements, however, finding such median is an expensive task that negates the advantages of using it at all (Shaffer, 2011).
Choosing a random pivot gives a good performance in practice (Shaffer, 2011), but finding such pivot is also an expensive task.
Choosing the first, the last, or the middle element as the pivot is O(1) simple operation, but it ignores the element distribution in the array.
The best in-practice pivot selection according to (Shaffer, 2011) is the median of three, where the first, the last, and the middle elements are sorted and the median is selected as the pivot, which is also an O(1) simple operation.