In this article, we are going to take you through one of the most efficient sorting algorithm – quick sort. Quick sort algorithm sorts the data step by step and performs a complete analysis of it. This sorting algorithm uses the idea of divide and conquer. As the name suggests, it divides the entire array into two halves and then merges it. It does so by finding a pivot element which divides the array into two halves in such a way that elements to the left of pivot are smaller than the pivot, while elements to the right are larger than it. It is an efficient sorting algorithm and is also known as partition exchange sort.

Algorithm

The below image gives an insight into the working of quick sort algorithm.

• Pick an element called pivot from the array. There are many ways to choose a pivot element, we usually choose the middle element in the array.
• Reorder the array in such a way that the elements left to the chosen element are lesser and the elements to the right of the pivot is more. This is called portioning the array.
• Recursively apply the above given two steps to the smaller subarrays until you get the desired result.

Code

On executing the code, below output is available.

Time Complexity

For an array of n elements, Order of quick sort is f(n)=O(nlog2n)

Worse case would yield O(n2)

Average case will be O(nlogn)

References

Detailed analysis of Quick Sort

Interactive demo of quick sort

This site uses Akismet to reduce spam. Learn how your comment data is processed.