Real-life Example Based on Quick Sort
Imagine you're in charge of organizing books in a library. You have a big pile, and you need to put them in order on the shelves. You pick a book from the middle and start comparing other books to it. Books that should come before it go on one side, and those that come after go on the other. You then pick another book from each smaller pile and do the same thing again and again until all books are neatly arranged. This is similar to how the quick sort algorithm works. It picks a 'pivot' item, sorts items around it, and keeps doing this in smaller groups until everything is in order. This method is not just for books but is used in computer programs to sort lists of data, making it easier to find and use the information they contain.
Quick Sort Algorithm
Quick sort is a popular sorting method in computer programming. It's known for its efficiency and is widely used in various applications. The algorithm follows a simple process of picking a single element from the list as a pivot and then arranging the rest of the elements around this pivot so that elements on one side are smaller and on the other side are larger. This process, called partitioning, is then recursively applied to the smaller lists on either side of the pivot.
How Quick Sort Algorithm Works?
-
Pivot Selection: The first step is to choose a pivot element. This can be any element from the list, such as the first, last, or a random element.
-
Partitioning: Rearrange the list so that all elements less than the pivot come before it and all elements greater come after it. After this step, the pivot is in its final position.
-
Recursive Sort: Apply the same steps to the sub-lists created on either side of the pivot. This process is repeated until the sub-lists contain only one element and no further partitioning is possible.
-
Combining: Since the algorithm works by modifying the list in place, no combining step is needed. The list becomes fully sorted once all the recursive calls are completed.
The efficiency of quick sort lies in its divide-and-conquer approach, which breaks down a big problem (sorting a large list) into smaller problems (sorting smaller sub-lists) and solves each efficiently.
Example
This example will sort an array of integers using quick sort. It includes functions for partitioning the array and for the recursive quick sort algorithm.
C
/******************************************************************************
Welcome to GDB Online.
GDB online is an online compiler and debugger tool for C, C++, Python, Java, PHP, Ruby, Perl,
C#, OCaml, VB, Swift, Pascal, Fortran, Haskell, Objective-C, Assembly, HTML, CSS, JS, SQLite, Prolog.
Code, Compile, Run and Debug online from anywhere in world.
*******************************************************************************/
#include <stdio.h>
// Function to swap two elements
void swap(int* a, int* b) {
int t = *a;
*a = *b;
*b = t;
}
// This function takes the last element as pivot, places
// the pivot element at its correct position in sorted array,
// and places all smaller elements to left of pivot and all
// greater elements to right of pivot.
int partition(int arr[], int low, int high) {
int pivot = arr[high]; // pivot
int i = (low - 1); // Index of smaller element
for (int j = low; j <= high - 1; j++) {
// If current element is smaller than the 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);
}
// The main function that implements QuickSort
// arr[] --> Array to be sorted,
// low --> Starting index,
// high --> Ending index
void quickSort(int arr[], int low, int high) {
if (low < high) {
// pi is partitioning index, arr[p] is now
// at right place
int pi = partition(arr, low, high);
// Separately sort elements before
// partition and after partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
// Function to print an array
void printArray(int arr[], int size) {
int i;
for (i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
// Driver program to test above functions
int main() {
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
printf("Sorted array: \n");
printArray(arr, n);
return 0;
}
You can also try this code with Online C Compiler
Output
^ASorted array:
1 5 7 8 9 10
This code snippet begins by defining a swap function to exchange the values of two integer variables. The partition function then arranges elements around the pivot, which is chosen to be the last element of the array segment being sorted. The quickSort function implements the recursive quick sort algorithm, calling itself for the sub-arrays before and after the pivot's final position. Finally, printArray displays the sorted array.
How to Choose Pivot in Quick Sort Algorithm?
Choosing the right pivot in quick sort is crucial because it can significantly affect the algorithm's efficiency. The pivot is the element around which the list is partitioned; hence, its position can make the sorting process faster or slower. There are several strategies to pick a pivot:
First Element as Pivot
This is the simplest method where the first element of the array or sub-array is chosen as the pivot. While easy to implement, it's not always the most efficient, especially if the array is already or nearly sorted.
Last Element as Pivot
Similar to the first element, but the last element of the array or sub-array is chosen. This method has similar pros and cons to using the first element as the pivot.
Random Element as Pivot
Selecting a random element as the pivot can often help avoid the worst-case performance of quick sort on nearly sorted arrays. It's more unpredictable but tends to work well on average.
Median as Pivot
This approach involves choosing the median of the first, last, and middle elements of the array or sub-array as the pivot. It's a more sophisticated method that can lead to better performance by aiming for a pivot that's closer to the actual median of the values.
Median-of-Medians as Pivot
This advanced technique is used to find an approximate median as the pivot, ensuring that the partitions are reasonably balanced. While effective, it's more complex to implement and typically used in specialized cases.
Advantages of Quick Sort Algorithm :
Efficiency
Quick sort is known for its speed, especially on large lists. It can sort a big number of elements much faster than other simple sorting algorithms like bubble sort or insertion sort.
In-place Sorting
It doesn't require much additional space to perform the sorting. This means it modifies the input list directly, saving memory which makes it a good choice for systems with limited space.
Divide & Conquer
This strategy breaks down a big problem (sorting the entire list) into smaller problems (sorting smaller sub-lists), solving them individually, and then combining the results. This approach is usually very efficient.
Easily Implementable
Quick sort can be implemented easily in various programming languages, making it a versatile tool for developers.
Good Average Case
While the worst-case performance (O(n²)) happens on specific list orders, in the average and best cases, quick sort runs in O(n log n) time, which is highly efficient.
Adaptable
With slight modifications, quick sort can be adapted to sort lists of complex objects, handle duplicates more efficiently, or even parallelize the sorting process to take advantage of multi-core processors.
Disadvantages of Quick Sort Algorithm
Worst-Case Performance
In the worst-case scenario, such as when the list is already sorted or nearly sorted, and the pivot selection is unfortunate, quick sort can degrade to O(n²) performance, which is much slower compared to other efficient sorting algorithms like merge sort.
Sensitive to Pivot Choice
The efficiency of quick sort heavily depends on the choice of the pivot. An unfortunate choice can lead to unbalanced partitions, resulting in decreased performance.
Not Stable
Quick sort is not a stable sort, meaning that equal elements might not retain their original order in the sorted list. This could be problematic in certain applications where the order of equal elements is important.
Recursion Overhead
The algorithm uses recursion to sort the sub-lists. Deep recursion can lead to a significant amount of overhead and, in extreme cases, can cause a stack overflow error.
Inconsistent Performance
The performance of quick sort can vary significantly depending on the input data and the method used for selecting the pivot, making it less predictable than some other sorting algorithms.
Not Always the Best for Small Lists
For very small lists, simpler sorting algorithms like insertion sort might be more efficient due to lower overhead.
Frequently Asked Questions
Why is quick sort faster than other sorting algorithms like bubble sort?
Quick sort is generally faster because it uses a divide-and-conquer approach to sort subsets of the list independently, which significantly reduces the total number of comparisons and swaps needed.
Can quick sort be used for sorting linked lists?
Yes, quick sort can be adapted to sort linked lists. The main difference in implementation involves the way elements are swapped and partitioned, as linked lists allow for efficient insertion and deletion operations.
How can the worst-case performance of quick sort be avoided?
The worst-case performance of quick sort can often be mitigated by choosing the pivot more carefully, such as using the median-of-three method or selecting a random pivot, which helps ensure more balanced partitions.
Conclusion
In this article, we talked about the quick sort algorithm in detail. We started with real-life examples to understand its concept, we moved on to discussing the algorithm's steps, implementing it in C, and how to choose an effective pivot. We also looked at the significant advantages that make quick sort a preferred choice in programming, despite its disadvantages, which include potential inefficiency with unfortunate pivot choices and the algorithm's non-stable nature.
You can refer to our guided paths on the Coding Ninjas. You can check our course to learn more about DSA, DBMS, Competitive Programming, Python, Java, JavaScript, etc. Also, check out some of the Guided Paths on topics such as Data Structure andAlgorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc., as well as some Contests, Test Series, and Interview Experiences curated by top Industry Experts.
8+ registered 