Quick Sort📜
Not so quick actually, but yeah this algorithm is used to sort an array/list.
Time Complexity
- Average case O(n log n)
- Worst-case O(n²).
Explanation
At the top two main operations are happing in the quick sort, one is the partition which places an element to its fixed position, and that operation takes O(n). And second is the actual divide and conquer which in the best/average case will divide the list into two parts, and perform the same operation on either side of the partition.
So, considering the above lines in the mind, in the best/average case quicksort will take O(n * n/2), where first n is from the first operation and n/2 from the divide and conquer which we can also write as O(n log n).
And in the worst case, which is when the array/list is already sorted and we are using 0 or n-1 index of the list as a pivot (where n is the size of the list), in that case, the time complexity will be O(n²), because again two operations will be happing the first one will remain the same but the divide and conquer one won’t be happing because the list is already sorted and at each level, we are just creating only one side of the partition, and it will happen for all the elements, so the second operation will also take O(n). Combining both the operation we get O(n²).
There are two recommendations to avoid the worst case.
- Always use the middle index as the pivot
- Choose the pivot Randomly.
