Quick Sort – Divide and Conquer Approach with Code and Analysis

on

 



Quick Sort – Divide and Conquer Approach with Code and Analysis

Sorting is one of the most important operations in computer science. Among the various algorithms available, Quick Sort is widely known for its speed and efficiency. It follows the divide and conquer technique, making it one of the most preferred sorting algorithms in real-world applications.

What is Quick Sort

Quick Sort is a comparison-based sorting algorithm that works by dividing the array into subarrays and sorting them independently. The main idea is to select a pivot element, partition the array around the pivot, and then recursively sort the subarrays.

Step-by-Step Working

Let’s take an example array: [7, 3, 9, 2, 5]

Steps:

  1. Choose a pivot element (for example, the last element = 5).

  2. Rearrange elements so that all smaller elements come before the pivot and all greater elements come after it.
    After the first partition, the array becomes [3, 2, 5, 9, 7].

  3. Recursively apply the same process to the left subarray [3, 2] and right subarray [9, 7].

  4. Continue until all subarrays are sorted.

Final sorted array: [2, 3, 5, 7, 9]

Partitioning Process

Partitioning is the key step in Quick Sort.
The pivot element is placed in its correct position in the sorted array, ensuring that smaller elements are on the left and larger elements are on the right.

Code Implementation

In Python

def partition(arr, low, high):
    pivot = arr[high]
    i = low - 1
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

def quick_sort(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)
        quick_sort(arr, low, pi - 1)
        quick_sort(arr, pi + 1, high)

# Example
arr = [7, 3, 9, 2, 5]
quick_sort(arr, 0, len(arr) - 1)
print("Sorted array:", arr)

In C++

#include <iostream>
using namespace std;

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++;
            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 pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int main() {
    int arr[] = {7, 3, 9, 2, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    quickSort(arr, 0, n - 1);
    cout << "Sorted array: ";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    return 0;
}

Time and Space Complexity

Case Time Complexity Explanation
Best Case O(n log n) When pivot divides array evenly
Average Case O(n log n) Typical scenario
Worst Case O(n²) When pivot is smallest or largest element
Space Complexity O(log n) Due to recursive stack calls

Characteristics of Quick Sort

  1. Follows divide and conquer approach.

  2. Performs sorting in-place (no extra array needed).

  3. Works efficiently on large datasets.

  4. Not a stable algorithm (equal elements may change their order).

Comparison with Other Sorting Algorithms

Feature Merge Sort Quick Sort Insertion Sort
Approach Divide & Conquer Divide & Conquer Incremental
Best Case O(n log n) O(n log n) O(n)
Worst Case O(n log n) O(n²) O(n²)
Space Used O(n) O(log n) O(1)
Stable Yes No Yes

Real-World Applications

  • Used in many library sorting functions.

  • Preferred for large datasets.

  • Suitable when memory usage must be minimized.

  • Ideal for systems requiring fast average performance.

Conclusion

Quick Sort is one of the fastest sorting algorithms in practice.
Its divide and conquer approach and in-place sorting capability make it highly efficient for large datasets. However, careful pivot selection is important to avoid worst-case scenarios.

Key Takeaways

  • Uses divide and conquer technique.

  • Average and best case time complexity: O(n log n).

  • Worst case time complexity: O(n²).

  • In-place, not stable, and efficient for large datasets.

[NOTE: Kindly cross check answers once from other source also, Quantity and Quality of answers also kindly check before use, specially 5 marks answers are not sufficient kindly add from your side, this gives just quick review]



ALSO CHECK

Insertion Sort

Merge Sort

Bubble Sort

Selection Sort


Comments

Post a Comment