Quick Sort Algorithm | Working, Applications & More (+Examples)

15 mins read

Sorting is a fundamental operation in computer science, and Quick Sort stands out as one of the most efficient and widely used sorting algorithms. It follows the divide-and-conquer approach, breaking down a problem into smaller subproblems and solving them recursively. The algorithm works by selecting a pivot element, partitioning the array into two halves—one with elements smaller than the pivot and another with elements greater than the pivot—and then sorting them independently.

In this article, we will explore the working principle of Quick Sort, its time complexity, advantages, and implementation in different programming languages to understand why it remains a go-to choice for sorting large datasets.

Understanding Quick Sort Algorithm

Quick Sort in data structures is a divide-and-conquer sorting algorithm that efficiently arranges elements in ascending or descending order. The key idea behind Quick Sort is choosing a pivot and partitioning the array around it so that:

• Elements smaller than the pivot move to the left.
• Elements larger than the pivot move to the right.

This process is recursively repeated on the left and right subarrays until all elements are sorted.

Step-by-Step Breakdown

1. Choose a Pivot – Select an element as the pivot (this could be the first, last, middle, or a randomly chosen element).
2. Partition the Array – Rearrange elements such that all elements smaller than the pivot are on one side, and all elements larger than the pivot are on the other side.
3. Recursive Sorting – Apply the same logic to the left and right partitions until the array is completely sorted.

Real-Life Analogy: Arranging Books On A Shelf

Imagine you have a messy bookshelf and you want to organize the books based on their height. Instead of sorting all the books at once, you use a smart strategy:

1. Pick a Reference Book (Pivot) – Choose a book at random from the shelf.
2. Partition the Books – Move all books shorter than the chosen book to the left and all taller books to the right. The reference book is now in its correct position.
3. Repeat the Process – Now, take the left section and apply the same rule: pick another reference book, sort around it, and continue. Do the same for the right section.
4. Books Get Sorted Naturally – After repeating this process a few times, all the books will be neatly arranged from shortest to tallest.

Just like Quick Sort, this approach divides the problem into smaller parts and recursively organizes them, leading to an efficient sorting process.

Step-By-Step Working Of Quick Sort

Quick Sort is a divide-and-conquer algorithm that sorts an array by selecting a pivot and partitioning the elements around it. Here's how it works:

Step 1: Choose A Pivot Element

• Select an element from the array as the pivot (commonly, the first, last, or middle element).

Step 2: Partition The Array

• Rearrange elements such that:
• Elements smaller than the pivot move to its left.
• Elements greater than the pivot move to its right.
• The pivot now holds its final sorted position.

Step 3: Recursively Apply Quick Sort

• Apply Quick Sort on the left and right partitions separately.

Illustrative Example

Given Array:

arr = [8, 4, 7, 3, 5, 2, 6]

Step 1: Choose a Pivot

• Let's choose 5 as the pivot.

Step 2: Partitioning

• Move elements:
• [4, 3, 2] go to the left of 5.
• [8, 7, 6] go to the right of 5.
• Result after partitioning:

[4, 3, 2] 5 [8, 7, 6]

Step 3: Recursively Sort Left and Right Subarrays

1. Sorting Left Subarray [4, 3, 2]
• Pivot = 3
• After partitioning: [2] 3 [4]
2. Sorting Right Subarray [8, 7, 6]
• Pivot = 7
• After partitioning: [6] 7 [8]

Final Sorted Array

[2, 3, 4, 5, 6, 7, 8]

Implementation Of Quick Sort Algorithm

Here's a complete C++ implementation of the Quick Sort algorithm-

Code Example:

#include <iostream>
using namespace std;

// Function to partition the array
int partition(int arr[], int low, int high) {
    int pivot = arr[high]; // Choosing last element as pivot
    int i = low - 1; 

    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) { 
            i++;
            swap(arr[i], arr[j]); // Swap elements if smaller than pivot
        }
    }
    swap(arr[i + 1], arr[high]); // Place pivot in correct position
    return i + 1; 
}

// Quick Sort function
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);  // Recursively sort left subarray
        quickSort(arr, pi + 1, high); // Recursively sort right subarray
    }
}

// Function to print the array
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;
}

// Driver code
int main() {
    int arr[] = {8, 4, 7, 3, 5, 2, 6};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "Original Array: ";
    printArray(arr, n);

    quickSort(arr, 0, n - 1);

    cout << "Sorted Array: ";
    printArray(arr, n);

    return 0;
}

Output:

Original Array: 8 4 7 3 5 2 6
Sorted Array: 2 3 4 5 6 7 8

Explanation:

In the above code example-

1. We start by including the <iostream> library to enable input and output operations.
2. The partition function is responsible for rearranging the array around a pivot element, which is chosen as the last element of the array.
3. We initialize i to low - 1 to track the position where smaller elements should be placed.
4. We iterate through the array from low to high - 1, swapping elements that are smaller than the pivot with the element at i + 1.
5. After the loop, we swap the pivot element with arr[i + 1], ensuring that elements to the left are smaller and elements to the right are greater.
6. The quickSort function recursively sorts the left and right subarrays by choosing a partition index using partition.
7. The base condition if (low < high) ensures that recursion stops when the subarray has one or zero elements.
8. The printArray function iterates through the array and prints each element, followed by a newline for better readability.
9. In the main function, we define an array {8, 4, 7, 3, 5, 2, 6} and determine its size using sizeof(arr) / sizeof(arr[0]).
10. We print the original unsorted array using printArray.
11. We call quickSort on the entire array, passing the first and last index as arguments.
12. Finally, we print the sorted array to verify the result.

Time Complexity Analysis Of Quick Sort

Quick Sort is a highly efficient divide-and-conquer sorting algorithm. Its performance largely depends on how well the pivot divides the array. Let's analyze its time complexity in different scenarios.

Why Choosing A Good Pivot Matters

The efficiency of Quick Sort depends on selecting a good pivot, which ensures that the array is divided into balanced partitions.

1. Good Pivot (Middle Element, Median, or Randomized Selection) → O(n log n)
• The pivot splits the array evenly, reducing the recursion depth.
• Since each partition is about half the size of the previous, the number of recursive calls is log(n).
• The overall complexity remains O(n log n).
2. Bad Pivot (Smallest or Largest Element) → O(n²)
• The pivot causes one partition to have n-1 elements and the other to have 0.
• This results in n recursive calls, with each call taking O(n) operations.
• This leads to the worst-case complexity of O(n²).

Advantages Of Quick Sort Algorithm

Quick Sort is one of the most efficient sorting algorithms due to its unique approach. Here are its key advantages:

1. Faster in Practice

• Quick Sort has an average-case time complexity of O(n log n), making it significantly faster than other sorting algorithms like Bubble Sort (O(n²)) and Insertion Sort (O(n²)) for large datasets.
• It outperforms Merge Sort in many real-world applications due to better cache efficiency.

2. In-Place Sorting (Low Memory Usage)

• Quick Sort does not require extra memory like Merge Sort (which needs O(n) additional space for merging).
• It sorts the array by swapping elements within the same array, requiring only O(log n) auxiliary space for recursion.

3. Efficient for Large Datasets

• Quick Sort is widely used in large-scale applications such as databases, search engines, and sorting libraries because of its efficiency.
• It is a preferred choice for sorting large datasets compared to Heap Sort and Merge Sort.

4. Suitable for Parallel Processing

• Quick Sort can be efficiently implemented using multi-threading by sorting left and right subarrays in parallel, improving performance.

5. Better Cache Performance

• Quick Sort works efficiently with modern CPU architectures due to better locality of reference, reducing cache misses.
• This makes it faster than Merge Sort in practical scenarios, even though both have an O(n log n) time complexity.

6. Foundation for Library Implementations

• Many standard sorting functions in programming languages use Quick Sort or a variant of it.
• C++ STL (std::sort) uses a hybrid of Quick Sort and Heap Sort.
• Java’s Arrays.sort() for primitives is based on a tuned Quick Sort.

Disadvantages Of Quick Sort Algorithm

Despite its efficiency, Quick Sort has some drawbacks that can impact performance in certain scenarios. Here are its key disadvantages:

1. Worst-Case Time Complexity: O(n²)

• If the pivot is poorly chosen, such as always picking the smallest or largest element in an already sorted array, Quick Sort can degrade to O(n²), making it much slower than Merge Sort (O(n log n)).
• This happens when the partitioning is highly unbalanced, leading to inefficient recursion.
• Solution: Use a random pivot or the median-of-three method to improve performance.

2. Not Stable

• Quick Sort is not a stable sorting algorithm, meaning it does not preserve the relative order of equal elements.
• For example, if sorting [(A, 5), (B, 5), (C, 3)], Quick Sort might swap (A,5) and (B,5), losing their original order.
• Solution: If stability is required, consider Merge Sort or Insertion Sort.

3. Recursive Overhead

• Quick Sort is a recursive algorithm, and deep recursion can lead to stack overflow for large datasets, especially in languages with limited stack size.
• In the worst case (e.g., already sorted or reverse-sorted input with a poor pivot choice), the recursion depth can reach O(n). 
• Solution: Use tail recursion optimization or switch to an iterative approach with a manual stack.

4. Performance Degrades for Small Arrays

• Quick Sort performs poorly on small datasets (typically n < 10), as the recursive overhead outweighs its efficiency.
• In such cases, Insertion Sort is often faster because it has a lower constant factor.
• Solution: Many implementations switch to Insertion Sort when subarrays are below a threshold (e.g., 10 elements).

5. Extra Space for Recursive Calls (O(log n))

• While Quick Sort is in-place, its recursive function calls require O(log n) additional stack space.
• This is still better than Merge Sort (which needs O(n) extra space), but it can still be a limitation for extremely large arrays.
• Solution: Use iterative Quick Sort to avoid recursion overhead.

Quick Sort vs. Other Sorting Algorithms

In this section we will compare quick sort algorithm with different sorting algorithms:

1. Quick Sort Vs. Merge Sort

Key Takeaway:

• Quick Sort is faster in practice due to better cache locality.
• Merge Sort is better for linked lists and guarantees O(n log n) complexity in all cases.

2. Quick Sort Vs. Bubble Sort

Key Takeaway:

• Quick Sort is far superior to Bubble Sort in almost all cases.
• Bubble Sort is only useful for small datasets or teaching sorting concepts.

3. Quick Sort Vs. Heap Sort

Key Takeaway:

• Quick Sort is faster in most general sorting cases.
• Heap Sort is preferred when guaranteed O(n log n) worst-case time is needed, such as real-time applications.

Applications Of Quick Sort Algorithm

Quick Sort is widely used in various domains due to its efficiency, in-place sorting capability, and adaptability. Here are some of its key applications:

1. Sorting Large Datasets Efficiently

• Quick Sort is used in databases and search engines to handle massive datasets due to its O(n log n) average-case time complexity.
• Example: Sorting millions of records in MySQL, PostgreSQL, and MongoDB.

2. Competitive Programming & Libraries

• Many programming languages use Quick Sort or its optimized versions in their standard sorting functions:
• C++ STL (std::sort)– A hybrid of Quick Sort and Heap Sort.
• Java (Arrays.sort())– Uses a variation of Quick Sort for primitive data types.
• Python (sorted() and list.sort()) – Uses Timsort, which is inspired by Merge Sort and Quick Sort.

3. Operating Systems (OS) & File Systems

• Quick Sort is used in file system operations, such as sorting files by name, size, or date.
• Memory management in operating systems utilizes Quick Sort for paging algorithms.

4. Graph Algorithms & Computational Geometry

• Quick Sort helps in sorting edges in Kruskal’s algorithm (used in finding Minimum Spanning Trees).
• Used in Convex Hull algorithms (like Graham’s scan) for sorting points based on coordinates.

5. Artificial Intelligence & Machine Learning

• In AI, Quick Sort is used for feature selection, where data needs to be sorted based on importance scores.
• Helps in clustering algorithms and sorting training datasets efficiently.

6. Sorting in E-Commerce & Finance

• E-commerce platforms like Amazon, Flipkart, and eBay use Quick Sort for sorting products by price, popularity, or ratings.
• Financial systems use Quick Sort in order matching engines to process buy/sell orders in stock markets.

7. DNA Sequencing & Bioinformatics

• In genomic research, Quick Sort is used to arrange DNA sequences based on length, genetic markers, or frequency.

8. Image Processing & Computer Vision

• Used in median filtering, where pixel intensities need to be sorted to remove noise.
• Helps in object detection and pattern recognition by sorting feature vectors efficiently.

9. Cybersecurity & Data Encryption

• Quick Sort helps in sorting cryptographic keys for secure data transmission.
• Used in sorting logs in intrusion detection systems (IDS) to detect unusual activity.

Conclusion

Quick Sort stands out as one of the most efficient and widely used sorting algorithms due to its divide-and-conquer approach, in-place sorting capability, and excellent average-case performance of O(n log n). While it may suffer from a worst-case complexity of O(n²) in poorly chosen pivot scenarios, techniques like randomized pivot selection help mitigate this issue.

Its versatility makes it a preferred choice in databases, competitive programming, operating systems, artificial intelligence, and even bioinformatics. When compared with other sorting algorithms like Merge Sort, Bubble Sort, and Heap Sort, Quick Sort proves to be a fast and memory-efficient option for most practical applications.

However, choosing the right sorting algorithm depends on the specific use case. If stability is required, Merge Sort might be preferable, while Heap Sort guarantees a strict O(n log n) worst-case performance.

Ultimately, Quick Sort remains a go-to algorithm for large-scale sorting problems where speed and efficiency matter. Understanding its strengths and limitations ensures we use it effectively in real-world applications.

Frequently Asked Questions

Q. Why is Quick Sort preferred over Merge Sort in many practical scenarios?

Quick Sort is often preferred over Merge Sort in practical applications because:

• It is in-place, meaning it requires O(log n) auxiliary space, whereas Merge Sort requires O(n) extra space.
• It has better cache locality, as it accesses memory in a sequential manner, making it faster on modern hardware.
• On average, Quick Sort performs O(n log n) operations, which is comparable to Merge Sort, but with less overhead.

However, if stability is required (i.e., preserving the order of duplicate elements), Merge Sort is a better choice.

Q. What are the different pivot selection strategies in Quick Sort?

Choosing a good pivot is crucial to Quick Sort’s performance. Common pivot selection strategies include:

• First element as pivot – Simple but can lead to worst-case performance if the array is already sorted.
• Last element as pivot – Similar to the first-element strategy, with the same risk of poor performance.
• Random element as pivot – Helps avoid worst-case scenarios by selecting a pivot randomly.
• Median-of-three pivot – Chooses the median of the first, middle, and last elements, reducing the likelihood of worst-case behavior.

Using randomized or median-of-three pivot selection is recommended for optimizing performance.

Q. What is the worst-case time complexity of Quick Sort, and how can it be avoided?

The worst-case time complexity of Quick Sort is O(n²), which happens when:

• The pivot always partitions the array into highly unbalanced subarrays.
• The array is already sorted (ascending or descending), and the first or last element is chosen as the pivot.

How to avoid it?

• Use randomized Quick Sort, which selects a random pivot to reduce the chance of worst-case behavior.
• Implement median-of-three partitioning, where the pivot is chosen as the median of three selected values.
• Use hybrid sorting, where Quick Sort is applied until the array size is small, and then another sorting method like Insertion Sort is used.

Q. Is Quick Sort a stable sorting algorithm? Why or why not?

No, Quick Sort is not stable because it does not guarantee the relative order of equal elements in the sorted array.

Why?

• During partitioning, elements may be swapped across the pivot, altering their original positions.
• Stability is not preserved when elements with the same value are placed in different subarrays.

However, Stable Quick Sort can be implemented using additional memory, but this negates its key advantage of being an in-place sort. If stability is a requirement, Merge Sort is a better alternative.

Q. How does Quick Sort perform compared to Heap Sort in terms of efficiency?

Key Takeaway:

• Quick Sort is generally faster in real-world applications due to better cache locality.
• Heap Sort is used when a strict O(n log n) worst-case performance is required, such as in priority queues.

Suggested Reads: 

1. Difference Between Hashing And Encryption Decoded
2. 53 Frequently Asked Linked List Interview Questions With Answers 2024
3. Data Structure Interview Questions For 2024 [With Detailed Answers]
4. Tree Topology | Advantages & Disadvantages In Computer Network
5. Decoding Data Redundancy In DBMS| Causes, Advantages, Solutions
6. Machine Learning Algorithms: Techniques, Applications, And Insights