Tony Hoare, a British computer scientist, invented the QuickSort algorithm in 1959. The name "Quick-sort" stems from the fact that it can sort a list of data elements substantially faster (twice or three times faster) than any other sorting method.
Quicksort is one of the most efficient sorting algorithms. It works by breaking an array (partition) into smaller ones and swapping (exchanging) the smaller ones, depending on a comparison with the 'pivot' element picked.
By the end of this tutorial, you will have a better understanding of the fundamental technicalities of the Quick Sort with all the necessary details along with practical implementations.
What Is the Quick Sort Algorithm?
Quicksort is a highly efficient sorting technique that divides a large data array into smaller ones. A vast array is divided into two arrays, one containing values smaller than the provided value, say pivot, on which the partition is based. The other contains values greater than the pivot value.
Now, look at the working of the Quick-Sort algorithm to understand the Quick Sort better.
How Does Quick Sort Work?
To sort an array, you will follow the steps below:
- You will make any index value in the array as a pivot.
- Then you will partition the array according to the pivot.
- Then you will recursively quicksort the left partition
- After that, you will recursively quicksort the correct partition.
Let's have a closer look at the partition bit of this algorithm:
- You will pick any pivot, let's say the highest index value.
- You will take two variables to point left and right of the list, excluding pivot.
- The left will point to the lower index, and the right will point to the higher index.
- Now you will move all elements which are greater than pivot to the right.
- Then you will move all elements smaller than the pivot to the left partition.
And this is how the QuickSort algorithm works. Now implement this algorithm through a simple C++ code.
How to Implement the Quick Sort Algorithm?
You will be provided with an array of elements {10, 7, 8, 9, 1, 5}. You have to write a code to sort this array using the QuickSort algorithm. The final array should come out to be as {1, 5, 7, 8, 9, 10}.
Code:
// C++ implementation of QuickSort
#include <bits/stdc++.h>
using namespace std;
// A utility function to swap two elements
void swap(int* a, int* b)
{
int t = *a;
*a = *b;
*b = t;
}
/* This function takes the final pivot element, puts the pivot element in an ordered array, and places all smaller elements on the left side of the pivot, as well as all larger elements on the right of the pivot. */
int partition (int arr[], int l, int h)
{
int pivot = arr[h]; // pivot
int i = (l - 1); // Index of smaller element and indicates the right position of pivot found so far
for (int k = l; k <= h - 1; k++)
{
// When the actual element is less than the pivot
if (arr[k] < pivot)
{
i++; // increment index of smaller element
swap(&arr[i], &arr[k]);
}
}
swap(&arr[i + 1], &arr[h]);
return (i + 1);
}
//A function to implement quicksort
void quickSort(int arr[], int l, int h)
{
if (l < h)
{
//pi is a partitioning index, and
//arr[p] is now in the correct location.
int pi = partition(arr, l, h);
// Separately sort elements before
// partition and after partition
quickSort(arr, l, pi - 1);
quickSort(arr, pi + 1, h);
}
}
/* Function to print an array */
void print_array(int arr[], int size)
{
int i;
for (i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
int main()
{
int arr[] = {11, 13, 16, 1, 3, 5, 9};
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
cout << "Sorted array: \n";
printArray(arr, n);
return 0;
}
You have now explored the working of Quick Sort with a code. Now you will see some of the advantages of the Quick Sort.
Quicksort Complexity
Quicksort is popular for its impressive average-case performance, making it a popular choice for sorting large datasets. It is a powerful sorting algorithm with a favorable average-case time complexity and versatile applications in various fields of computer science. Understanding its complexity and having code implementations in multiple programming languages can be valuable for students and professionals, allowing them to leverage Quicksort's efficiency in their projects and applications. To understand its complexity, we'll examine both time and space complexities.
a. Time Complexity
- Average Case: O(n*log(n))
- Worst Case: O(n^2)
- Best Case: O(n*log(n))
The average-case time complexity of Quicksort is O(n*log(n)), which is quicker than Merge Sort, Bubble Sort, and other sorting algorithms. However, the worst-case time complexity is O(n^2) when the pivot choice consistently results in unbalanced partitions. To mitigate this, randomized pivot selection is commonly used.
b. Space Complexity
Quicksort has a space complexity of O(log(n)) in the average case. This arises from the recursive function calls and the partitioning process. It can be O(n) due to an unbalanced partitioning leading to a deep recursion stack in the worst case.
Quicksort Applications
Quicksort's efficiency and adaptability make it suitable for many applications, including but not limited to:
- Sorting Algorithms: Quicksort is frequently used as a building block for hybrid sorting algorithms, such as Timsort (used in Python's built-in sorting function).
- Database Systems: Quicksort plays a vital role in database management systems for sorting records efficiently.
- Computer Graphics: Rendering and graphics applications often involve sorting operations, where Quicksort can be employed to optimize rendering performance.
- Network Routing: Quicksort can be utilized in various networking algorithms, particularly routing tables.
- File Systems: File systems use Quicksort to manage and organize files efficiently.
Quicksort Code in Python, Java, and C
Sample code implementations of Quicksort in Python, Java, and C are as follows. These examples showcase the algorithm's adaptability across different programming languages.
a. Quicksort in Python
def quicksort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quicksort(left) + middle + quicksort(right)
b. Quicksort in Java
public class QuickSort {
public static void quicksort(int[] arr, int low, int high) {
if (low < high) {
int pivotIndex = partition(arr, low, high);
quicksort(arr, low, pivotIndex - 1);
quicksort(arr, pivotIndex + 1, high);
}
}
public static int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
public static void main(String[] args) {
int[] arr = {3, 6, 8, 10, 1, 2, 1};
quicksort(arr, 0, arr.length - 1);
for (int num : arr) {
System.out.print(num + " ");
}
}
}
c. Quicksort in C
#include <stdio.h>
void swap(int* a, int* b) {
int t = *a;
*a = *b;
*b = t;
}
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j <= high - 1; j++) {
if (arr[j] < pivot) {
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}
void quicksort(int arr[], int low, int high) {
if (low < high) {
int pivotIndex = partition(arr, low, high);
quicksort(arr, low, pivotIndex - 1);
quicksort(arr, pivotIndex + 1, high);
}
}
int main() {
int arr[] = {3, 6, 8, 10, 1, 2, 1};
int n = sizeof(arr) / sizeof(arr[0]);
quicksort(arr, 0, n - 1);
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
What Are the Advantages of Quick Sort?
Let us discuss a few significant benefits of using Quick Sort and a few scenarios where Quick Sort is proven to be delivering the best performance.
- It is an in-place algorithm since it just requires a modest auxiliary stack.
- Sorting n objects takes only n (log n) time.
- Its inner loop is relatively short.
- After a thorough mathematical investigation of this algorithm, you can make a reasonably specific statement about performance issues.
What Are the Disadvantages of Quick Sort?
Despite it being the quickest algorithm, Quick Sort does a few downfalls. Let us address a few significant limitations that you should be considering before you implement Quick Sort in real-time.
- It is a recursive process. The implementation is quite tricky, mainly if recursion is not provided.
- In the worst-case scenario, it takes quadratic (i.e., n2) time.
- It is fragile in the sense that a slight error in implementation can go unreported and cause it to function poorly.
With this, you have come to an end of this tutorial. You will now look at what could be your next steps to master other sorting algorithms.
Next Steps
Your next stop in mastering data structures should be the selection Sort Algorithm. Using in-place comparisons, the selection sort algorithm divides the list into two parts, with the sorted half on the left and the unsorted half on the right.
If you are looking to enhance your software development skills further, we would highly recommend you to check out Simplilearn’s Full Stack Developer - MERN Stack. In collaboration with IBM, this course can help you hone the right skills and make you job-ready.
If you have any questions or require clarification on this "Merge Sort Algorithm" tutorial, please leave them in the comments section below. Our expert team will review them and respond as soon as possible.
FAQs
1. What Is a Quick Sort Algorithm?
Quick sort is a widely used and efficient sorting algorithm that employs a divide-and-conquer approach to sort an array or list of elements. The basic idea behind quick sort is to select a 'pivot' element from the array and partition the elements into two sub-arrays:
- one incorporating elements less than the pivot
- the other containing elements greater than the pivot.
2. What Is the Best Case and Worst Case in a Quick Sort Algorithm?
The best-case scenario for quick sort occurs when the pivot is chosen to divide the input array into roughly equal-sized sub-arrays consistently. In this case, the algorithm exhibits O(n log n), optimal performance with time complexity. This is because each recursion level divides the array into two roughly equal parts, leading to a logarithmic number of levels.
Conversely, the worst-case scenario for quick sort arises when the pivot is consistently chosen poorly, such as always selecting the smallest or largest element in the array. In this situation, Quick Sort may require O(n^2) comparisons and swaps to complete the sorting process, which could be more efficient. For example, this worst-case scenario can occur when sorting an already sorted array or an array with many duplicate elements.
3. What Is the Runtime of Quicksort?
The runtime or time complexity of quicksort depends on various factors, including the choice of pivot and the characteristics of the input data. In the average-case scenario, quicksort exhibits a time complexity of O(n log n), which makes it one of the fastest sorting algorithms for a wide range of inputs.
