The Quick Sort Algorithm

Quicksort is another sorting algorithm named so because it is significantly faster than any other common sorting algorithm, This algorithm uses the concept of Divide and Conquer and can be written recursively.

How this works is that it uses a pivot element from the list or array and partitions it into separate arrays. Then the elements less than the pivot element are moved to its left and those greater elements to its right. Once this happens the pivot is in its right position. However, it is not necessary that the elements moved to either side will be sorted, hence we need to repeat the process to actually sort the algorithm. Because of repeating the process, we see that every element has been a pivot element, so every element is at its right position.

Understanding with an example.

1. This is an unsorted array. To perform the quicksort algorithm we need to select a pivot, and for convenience, we usually take the first element as the pivot in this case 20.
2. We take two pointers, low at position 0 and high at position 6.
3. Low moves from left to right via incrementation and high moves from right to left via decrementation.
4. Value at low in 20, high is -22 and pivot is 20.
5. Partitioning:
6. To get the elements smaller than the pivot element in the partitioning function, we compare the element at position high to the pivot element, and if it’s less we replace the position of the element at high. In this case -22 < 20, so -22 will bow occupy position 0.

1. Now at this point shift to position low, begin with the position low+1, and compare the element there to the pivot element, if the element is greater than the pivot swap it to high. In this case 35 > 20, so 35 is moved to position 6

1. Note that no data is lost, because the element at position 6 is already at position 0 and vice versa, we can be sure not to lose data by alternating between the high and low position of the array.
2. Now we check if low and high have crossed each other. If they have, we stop traversing and the low position becomes the sorted position of the pivot. If not, then we go back to high and decrement it by one and compare the element at that position of the pivot element.
3. In this case 1<20, so 1 move’s to the current low position which is the index 1.

1. Switch back to high again and we look for the element greater than the pivot. We move directly to 55, where 55>20, so 55 movies to the current high position which is 5.

1. Now we check again if low and high have crossed each other. If they have, we stop traversing and the low position becomes the sorted position of the pivot. If not, then we go back to high and decrement it by one and compare the element at that position of the pivot element. (step — 4)
2. At this point low = 4 and high = 5, so we go to high to find an element less than the pivot element. However, the element is found at position 3, which means that high and low have crossed each other, so the current low position which is 4 becomes the sorted position for the pivot element 20.

Here we have completed our first partitioning. We, see that all the elements to the left of 20 are less than it and to right are greater. However the sorting is not complete, we need to repeat the entire process for the now created subarrays on the left and right of the pivot until each element has been the pivot element. After all the partitioning is complete, we will have our sorted array.

Algorithm

The quicksort algorithm can be written recursively and a function to partition and swap elements in the array is also written separately.

The quicksort algorithm.

1. quicksort (array A, low, high)
2. {
3. if(low<high)
4. {
5. p = partition(A, low, high)
6. quicksort (A, low, p — 1)
7. quicksort (A, p + 1, high)
8. }
9. }

Partitioning method algorithm.

1. partition (array A, low, high)
2. {
3. pivot = A[high]
4. i = low-1
5. for j = low to high -1 {
6. if (A[j] < pivot) {
7. i = i + 1
8. swap A[i] with A[j]
9. }
10. }
11. swap A[i+1] with A[high]
12. return i+1
13. }

Time Complexity Analysis of the Quicksort Algorithm

• Average Case: O(n*logn)
• This case occurs when elements of the array are neither in increasing nor decreasing order.
• Worst Case: O(n²)
• This occurs when the array is already sorted and the pivot is either the largest or the smallest element.
• Best Case: O(n*logn)
• Occurs when the pivot is the middle element or close to it.

Application of Quicksort Algorithm

• Commercial Computing
• Information Searching
• Anywhere where stable sort is not needed.