Quick sort

It is an algorithm of Divide & Conquer type.

Divide: Rearrange the elements and split arrays into two sub-arrays and an element in between search that each element in the left sub-array is less than or equal to the average element and each element in the right sub-array is larger than the middle element.

Conquer: Recursively, sort two sub-arrays.

Combine: Combine the already sorted array.

An array is sorted with a call to QUICKSORT(A, 1, A.length):

The work is done in the PARTITION procedure. A[r] will be the pivot. (Note that the end element of the array is taken as the pivot. Given random data, the choice of the position of the pivot is arbitrary; working with an end element simplifies the code):

Example Trace

Complexity Analysis
Time Complexity of Quick sort

• Case 1: The case when sizes of the sublist on either side of the pivot become equal occurs when the subarray has an odd number of elements and the pivot is right in the middle after partitioning. Each partition will have (n-1)/2 elements.

• Case 2: The size difference of 1 between the two sublists on either side of the pivot happens if the subarray has an even number, n, of elements. One partition will have n/2 elements with the other having (n/2)-1.

Space Complexity of Quick sort

It is worth taking some time to trace through and explain each step of this example of the PARTITION procedure, paying particular attention to the movement of the dark lines representing partition boundaries.

Continuing ...

• Best case scenario: The best case scenario occurs when the partitions are as evenly balanced as possible, i.e their sizes on either side of the pivot element are either are equal or are have size difference of 1 of each other.

  In either of these cases, each partition will have at most n/2 elements and the tree representation of the subproblem sizes will be as below:

The best-case complexity of the quick sort algorithm is O(n logn)

• Worst case scenario: This happens when we encounter the most unbalanced partitions possible, then the original call takes n time, the recursive call on n-1 elements will take (n-1) time, the recursive call on (n-2) elements will take (n-2) time, and so on. The worst case time complexity of Quick Sort would be O(n2).

The space complexity is calculated based on the space used in the recursion stack. The worst case space used will be O(n) . The average case space used will be of the order O(log n). The worst case space complexity becomes, when the algorithm encounters its worst case where for getting a sorted list, we need to make n recursive calls.