The average-case performance of Quick Sort is O(n log n). However, the worst-case performance of Quick Sort occurs when the pivot selected is either the smallest or largest element in the list. In this case, the partitioning step will result in one sub-list with n-1 elements and another sub-list with 0 elements. This will lead to N recursive calls, and therefore the time complexity will be O(n^2).
Two scenarios may cause the worst performance:
Array of all the same elements: In this scenario, the pivot element will always be the same as all the other elements in the array. This means that each partition will only remove one element from the array, resulting in a recursive tree with N levels (where N is the number of elements in the array). This gives a worst-case time complexity of O(N^2).
Array of already sorted elements: In this scenario, the pivot element will either be the smallest or largest element in the array, depending on the implementation of the algorithm. This will lead to a partition with one sub-array of size 0 and another sub-array of size N-1. This also results in a recursive tree with N levels and worst-case time complexity of O(N^2).
However, the following carefully designed algorithm can prevent the worst performance in the two scenarios. It is also an in-place algorithm, which means the algorithm will use only a small amount of additional memory to perform its operations. Here are the steps:
Choose a pivot element. This is a random element in the array.
Swap the pivot element and the first element in the array. The first element is the pivot now.
Define two pointers, one pointing to the second element of the array, and the other pointing to the last element of the array.
Repeat the following steps until the left_pointer is greater than or equal to the right_pointer:
Move the left_pointer to the right until it points to an element that is greater than or equal to the pivot.
Move the right_pointer to the left until it points to an element that is less than or equal to the pivot.
If the left_pointer is less than or equal to the right_pointer, then swap the elements at the left_pointer and right_pointer, and move both pointers one step towards each other.
Once the pointers have crossed each other, swap the first pivot element with the element at the right_pointer.
Recursively apply the same steps on the sub-arrays to the left and right of the pivot element.
Array of All the Same Elements
In the scenario of an array of all the same elements, the pivot element will be equal to all the other elements, which means that in step 4.a and 4.b, the pointers will never move. As a result, step 4.c will simply swap the two elements, and the pointers will move towards the center, thus effectively splitting the array into two equal sub-arrays.
Therefore, the algorithm can avoid the worst-case performance due to arrays of equal elements, and in fact, it will sort such arrays in O(NlogN) time, which is the average-case performance of the algorithm.
Array of Already Sorted Elements
To avoid this scenario, one can choose the pivot element randomly instead of always selecting the first or last element as the pivot. By choosing the pivot element randomly, the probability of selecting the smallest or largest element as the pivot is reduced, and the resulting partitions are more likely to be balanced. This helps to ensure that the worst-case performance is avoided and that the overall runtime is closer to the average-case performance of O(NlogN).
Another Detail
In step 4 of the algorithm, the while loop condition includes a scenario where both left_pointer and right_pointer point to the same element. This element may be greater than the pivot element. The loop exits after one iteration, ensuring that the right_pointer's element is less than or equal to the pivot. At this point, it can be swapped with the pivot.
