Quick Sort Algorithm
Quick Sort Algorithm
There are may versions of Quick sort, which is one of the most popular sorting methods due to its speed (O(N lgN) average, but O(N^2) worst case). Here’s the steps to follow:
- Pick a “pivot” item
- Partition the other items by adding them to a “less than pivot” sublist, or “greater than pivot” sublist
- The pivot goes between the two lists
- Repeat the quicksort on the sublists, until you get to a sublist of size 1 (which is sorted).
- Combine the lists — the entire list will be sorted
Quicksort is the quickest and one of the most efficient sorting algorithm. Similar to Merge sort, Quick sort follows Divide and conquer algorithm to sort the given array.
The quicksort algorithm is a sorting algorithm that sorts an array by choosing a pivot element, and partition the array around the pivot such that
Elements smaller than the pivot are moved to the left of pivot, and elements larger than the pivot are moved to the right of pivot.
It continues to choose a pivot element and break down the array into single-element array, before combing them back together to form a single sorted array.
Working Model of Quick Sort
Time Complexity of Quick Sort
Since similar to Merge sort, Quick sort follows divide and conquer algorithm, its complexity in average and best case is same as that of Merge sort which is O(nlogn).
Whereas in the worst case, its complexity is O(n2). This occurs when the given array is nearly or completely sorted.
Complexity Analysis of Quick Sort
For an array, in which partitioning leads to unbalanced sub arrays, to an extent where on the left side there are no elements, with all the elements greater than the pivot, hence on the right side.
And if keep on getting unbalanced sub arrays, then the running time is the worst case, which is O(n2)
Where as if partitioning leads to almost equal sub arrays, then the running time is the best, with time complexity as O(n*log n).
Worst Case Time Complexity [ Big-O ]: O(n2)
Best Case Time Complexity [Big-omega]: O(n*log n)
Average Time Complexity [Big-theta]: O(n*log n)
Space Complexity: O(n*log n)
Implementing Quick Sort Algorithm
Below we have a simple C program implementing the Quick sort algorithm:
// simple C program for Quick Sort
# include <stdio.h>
// to swap two numbers
void swap(int* a, int* b)
{
int t = *a;
*a = *b;
*b = t;
}
/*
a[] is the array, p is starting index, that is 0,
and r is the last index of array.
*/
void quicksort(int a[], int p, int r)
{
if(p < r)
{
int q;
q = partition(a, p, r);
quicksort(a, p, q);
quicksort(a, q+1, r);
}
}
int partition (int a[], int low, int high)
{
int pivot = arr[high]; // selecting last element as pivot
int i = (low - 1); // index of smaller element
for (int j = low; j <= high- 1; j++)
{
// If current element is smaller than or equal to pivot
if (arr[j] <= pivot)
{
i++; // increment index of smaller element
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}
// function to print the array
void printArray(int a[], int size)
{
int i;
for (i=0; i < size; i++)
{
printf("%d ", a[i]);
}
printf("\n");
}
int main()
{
int arr[] = {9, 7, 5, 11, 12, 2, 14, 3, 10, 6};
int n = sizeof(arr)/sizeof(arr[0]);
// call quickSort function
quickSort(arr, 0, n-1);
printf("Sorted array: n");
printArray(arr, n);
return 0;
}
