In Quick Sort Algorithm in Data Structures, an element is selected as a random element, and this element is placed at its correct position such that all the elements less than this are at its left and all the elements greater than this are at its right.
We can select any element as the pivot element whether it be first, last, or any random element. But generally, the last element is selected as a random element and is correctly placed.
After this, the same thing is done for the right portion (from the pivot element) of the array as well as for the left portion.
This process continues till each subarray contains a single element.
Now, we will understand this better by taking an example –
Let us consider an unsorted array –
First, we will consider the last element as the pivot element.
We will now fix this pivot element at its correct position.
Now, the same process continues for the left sub-array as well as the right subarray.
After this, the same process is recursively called for the left sub-array as well as the right sub-array. In the left sub-array, the last element is again selected as the pivot element. But here, as the left sub-array contains only a single element so no comparisons are to be made and the left sub-array is already sorted.
For the right subarray, the last element, i.e., 18 is selected as the pivot and it will be fixed at the right position. This process will continue till the whole array is sorted.
Now, we will understand the code for this algorithm –
// Quick sort in C++
#include <iostream>
using namespace std;
void swap(int *a, int *b) {
int t = *a;
*a = *b;
*b = t;
}
void printArray(int array[], int size) {
int i;
for (i = 0; i < size; i++)
cout << array[i] << " ";
cout << endl;
}
int partition(int array[], int low, int high) {
int pivot = array[high];
int i = (low - 1);
for (int j = low; j < high; j++) {
if (array[j] <= pivot) {
i++;
swap(&array[i], &array[j]);
}
}
swap(&array[i + 1], &array[high]);
return (i + 1);
}
void quickSort(int array[], int low, int high) {
if (low < high) {
int pi = partition(array, low, high);
quickSort(array, low, pi - 1);
quickSort(array, pi + 1, high);
}
}
int main() {
int data[] = {9,3,12,18,5};
int n = sizeof(data) / sizeof(data[0]);
cout << "Unsorted Array: \n";
printArray(data, n);
quickSort(data, 0, n - 1);
cout << "Sorted array in ascending order: \n";
printArray(data, n);
}
Output –
3 5 9 12 18
Time Complexity Analysis of Quick Sort Algorithm–
Best Case – O(n*logn)
Avg Case – O(n*logn)
Worst Case – O(n^2)
Space Complexity Analysis of Quick Sort Algorithm –
O(logn)
So, in this article, we learned about the quick sort algorithm. We will learn other sorting algorithms in upcoming articles.
