When does the worst case of QuickSort occur?
QuickSort is a type of Divide and Conquer algorithm. It works by picking an element as pivot. It then partitions the given array around the picked pivot. There are many different versions of quicksort. Then differ in the way they pick pivot. QuickSort will pivot if four different ways:
- Always pick first element as pivot
- Always pick last element as pivot
- Pick a random element as pivot
- Pick median as pivot
Regardless of what it pick, the key element in QuickSort is partition(). The target of partitions is to put x at its correct position in a sorted array and put all the elements smaller than x before x, and put all elements greater than x after x, after it has been given an array and an element x of array as pivot.
Now there are times, when QuickSort might fail. Some of the worst cases of Quicksort might occur in following cases:
- When one part after partition contains all elements and other part is empty
- Array is already sorted in same order.
- Array is already sorted in reverse order.
- All elements are same