Introduction to Quicksort Algorithm
Sorting is organizing the data in a systematic manner, in data structures we have various kinds of sorting algorithms. Quick sort is one of the widely implemented, quick, and efficient algorithms.
QuickSort is an in-place sorting algorithm that works upon the divide and conquers paradigm. The divide and conquer approach divides the problem into subproblems and it continuously divides the problem until it becomes a unit problem, then it solves or conquers the problems easily. After resolving the problem the results are combined to provide the result of the original problem. Quick sort is in-place because it does not require extra memory space for solving the problem, as it is swapping the elements without using any extra memory space.
You can also explore- Selection Sort Algorithm (With Code)
Quick sort works over a simple idea, i.e.
- Choose a pivot (key) element.
- Partition(divide) the array using a partitioning algorithm, such that all the elements smaller than the pivot element are on the left-hand side of the pivot element and all the elements greater than the pivot element are on the right-hand side of the pivot element.
- Repeat this division process recursively for all the subarrays until each subarray contains one element.
- Till this time, all the elements in each subarray would be sorted.
- The resulting array can be obtained by combining all the sub-arrays.
General implementation of the quick sort algorithm sorts all the elements in ascending order, this can be changed by modifying the logic of the program.
Working of QuickSort
Choose Pivot element
There are various ways to choose a pivot element. Quick sort itself has several versions based on different ways of choosing elements, some of the most common methods are as follows:
- Choose the first element of the array as the pivot element.
- Select the last element of the array as a pivot element.
- Choose the median element as the pivot element.
- Select any random element as a pivot element.
You can also explore – Bubble Sort Algorithm (With Code)
Partition Algorithm:
There can be multiple ways to perform partition, but it has common logic, i.e. start from the leftmost element, take a note of the smallest element, while traversing from left to right if you find any element smaller than I, swap the current element with I, else ignore the current element and continue traversing.
The partition algorithm is used to divide the array and then rearrange the sub-arrays. Here we are constructing a partition function that places the selected pivot element at its correct position and ensures that all the elements smaller than the pivot are in the sub-array left to the pivot and all the elements greater than the pivot is in the sub-array right to the pivot element.
Partition Algorithm:
// a is the array, x is the smallest index of array or lower bound, and y is the highest index of array or upper bound
Partition (a, x, y) { K= a [x]; // K is pivot element i = x; j = y;
while (i < j) { while (a [i] <= K) { i++; } while (a [j] > K) { j--; } if (i < j) { swap(a [i], a [j]); } }swap(a [x], a [y]);return;}
Best-suited Data Structures and Algorithms courses for you
Learn Data Structures and Algorithms with these high-rated online courses
Illustration of Algorithm using Example:
Example: Consider the following array and sort it using the QuickSort algorithm.
arr [] = {20, 70, 40, 80, 50, 60 }
Solution: Select the last element as the pivot element. The array can be visualized as:
The last or right-most elements are selected as pivot elements. So, the array will be traversed from left to right and all the elements will be rearranged such that all the elements smaller than the pivot element will be on the left side of the pivot element. And all the elements greater than the pivot are on the right side of the pivot element.
When a[i]<= K, then i++, or a[j]> K, then j–, else swap a[x], a[y]
Here, 20 will be swapped with 60.
Now, the Partition algorithm will be applied to each Unsorted array recursively until all the sub-array have a single element.
So, from the above, it might be easily understood, how the partition is taking place in each sub-array and sorting the array.
At last, after combining all the elements, the resulting sorted array would be like:
You can also explore – Insertion Sort Algorithm (With Code)
Time Complexity:
Best Case: O (nlogn), The algorithm performs best when the pivot element is always in the middle or near to middle element.
Average Case: O(nlogn), The algorithm performs average when the array is neither properly ascending nor in descending order.
Worst Case: O(n2), The algorithm performs worst when the pivot element is always either the greatest or smallest element in the array. So, when a partitioning algorithm is applied to such an array, one partition will have one element and the other partition would have an n-1 element, which will lead the algorithm to run (n2) time.
Space Complexity:
Quicksort has O(nlogn) space complexity, and it is unstable in nature as it the swapping is done according to the pivot element’s position without considering the original position of the elements.
Applications:
- QuickSort is the fastest algorithm.
- It has a good locality of reference for arrays.
- Event-driven simulation and operational searches.
- Implementation of Primitive type methods.
- Large numerical computations and scientific research.
This is a collection of insightful articles from domain experts in the fields of Cloud Computing, DevOps, AWS, Data Science, Machine Learning, AI, and Natural Language Processing. The range of topics caters to upski... Read Full Bio
Top Picks & New Arrivals
