In this tutorial, we are going to look at another sorting algorithm called Quick sort algorithm. It is an in-place sorting algorithm developed by British computer scientist Tony Hoare in 1959 and published in 1961. This algorithm is basically based on divide and conquer strategy. In this strategy we divide the problem into smaller parts, solve the problem for each smaller part and then merge all smaller solved parts into one. It is known as the fastest of all the sorting algorithms and hence widely used for quick and efficient searching. We will understand more about this algorithm in below section with the help of detailed examples.

 

What is the Quick Sort Algorithm [Explained with examples]

Also Read: What is Bubble Sort Algorithm [Explained with examples]

As we know the quick sort algorithm is based upon divide and conquer strategy in which the unsorted list is divided into smaller sub lists and we sort smaller sub lists and then all smaller sub lists are merged into one. It is a very quick and efficient way of sorting. It has average case time complexity of O(nlogn) and this is why it is the most practical and widely used sorting algorithm. Lets see how this quick sort algorithm works and uses divide and conquer strategy.

 

Working 

In this algorithm we assume the last element of an array as the pivot element and we try to arrange the array in such a way that the elements which are greater than the pivot should come in the right of pivot element and the elements which are smaller than the pivot element should come in left of pivot element. After that we divide the array into two sub arrays , one which contains the element smaller than the pivot element and another which contains the element greater than the pivot element. We repeat this process of rearranging and dividing till the sub array contains only one element.

Let's take one small example to get a basic understanding of how this quick sort algorithm works, later on we will understand this algorithm with the help of pseudocode then we will get to know how we rearrange and divide the array:-

arr[5]={7,9,11,5,6}

Let's assume element 6 as the pivot and after rearranging, element 6 finds its correct place and we divide the array into two parts , one part which is on the left side of the 6 and another part which is on the right side of the 6.

After dividing, left part contain only one element i.e. 5 that is why we will stop their and the right part contain 3 element that is 11 , 7 , 9 so further rearrangement and division is required , in right part again we will make 9 as pivot , will rearrange it and later on divide into two parts till the divided part contain only one element. If we write the red colored elements starting from left to right we will get our sorted list.

 

Pseudocode

Now we will understand how this rearranging and division of array works out. The Pseudocode for Quick Sort Algorithm is as follows :-

Quicksort(Arr[ ],start,end){
     if(start < end){
             P_index = Partition(Arr[ ], start, end)
             Quicksort(Arr[ ], start, P_index - 1 )
             Quicksort(Arr[ ], P_index + 1 , end)

     }
}
Partition(Arr,start,end){
Pivot = Arr[end]
P_index = start
     for i = start to end -1 {
             if (Arr[i] < = Pivot){
                    swap (Arr[i] , Arr[P_index])
                    P_index = P_index+1

             }
     swap(Arr[P_index] , Pivot)
     return P_index
     }
}

 

Explanation of Pseudocode

We first call the Quicksort function , inside this function we first call the Partition function which does rearrangement and returns the index of the correct position of the pivot element. Then this function calls itself for the left side of the pivot element and one more time calls itself for the right side of the pivot element. Let’s take the same example and sort with the help of pseudocode:-

 

Initial call is Quicksort(Arr[],0,4):-

Here, start = 0 and end = 4. Since start < end it calls Partition(Arr[ ], 0 , 4):-

Inside partition function, Pivot = Arr[end] and P_index = 0:-

Loop starts , for  i = 0 , nothing will happen because Arr[i] > Pivot:-

for  i =1 and 2 also nothing will happen but for i = 3 , we will swap Arr[i] with Arr[P_index] and P_index will become P_index + 1.

As for loop end when i reaches end -1 i.e. 3. After for loop we swap Arr[P_index] with Pivot:-

Partition index returns P_index which is 1. Now the Quicksort function calls itself for an array part which is before the P_index.

Quicksort(Arr[ ],0,0) , since start is not less than end it will simply return. Now Quicksort calls itself  for the array part which is after the P_index.

Quicksort(Arr[ ],2,4) , since start is less than end it will again repeat the same process it will again call Partition(Arr[ ],2,4) which will return the correct index of pivot element and this process will continue until the sub array contains only one element.

 

Implementation in C/C++

Here I am using Visual Studio Code to write the C/C++ program and the MinGW-w64 compiler is used for compiling the code.

a) C++ code snippet

Output

b) C code snippet

Output

 

Performance 

In the Quick sort algorithm, we divide the array into two parts , then again into two parts till only a single element is left so this division takes log(n) time where the Partition function takes (n) time as it contains one for loop. So the total average time complexity of Quicksort Algorithm is O(n*log(n)).

Average time complexity occurs when the elements are neither in increasing order nor in decreasing order. The best case time complexity occurs when the pivot element always lies in the middle of the array. The best case time complexity is O(n²).

The worst case time complexity occurs when the pivot element always lie at the extreme left or right position just because of this the array division also takes n time and total complexity becomes O(n*n) equivalent to O(n²). We are not using any extra space so time complexity is O(1).

 

Advantages

• Regarded as the best sorting algorithm
• No extra memory is required
• Average time complexity is O(n*logn)
• Very quick and efficient
• Cache performance is higher than other sorting algorithms

 

Disadvantages

• Very high time complexity in worst case
• It is not at all a stable algorithm
• Implementation can get extremely complicated if recursion not available
• Poorly picked pivot can lead to bad runtimes

 

Conclusion

Quick sort algorithm is based on divide and conquer strategy. It is a very fast and efficient algorithm. In quicksort , we repeatedly divide the array into smaller sub arrays until there is only one element present in the array and sort the array recursively. The best time complexity of quick sort algorithm is O(n*logn) and space complexity is O(1). In this tutorial, we have seen what is quick sort algorithm and how it works with the help of detailed examples.