Quick Sort | Code and Explanation | C++ Course - 19.2

People & Blogs

Quick Sort | Code and Explanation | C++ Course - 19.2

Introduction

Hello everyone! Today, we are going to dive deep into Quick Sort, a fundamental sorting algorithm in computer science. We'll break down the steps involved in Quick Sort, understand the underlying principles, and see how it can be implemented in C++.

Basic Concept of Quick Sort

The central idea behind Quick Sort is to select a 'pivot' element from the array and partition the other elements into two sub-arrays based on whether they are less than or greater than the pivot.

In a step-by-step manner:

  1. Choose a pivot: This can be any element from the array.
  2. Partitioning: Rearrange the array such that elements less than the pivot come before it, and elements greater come after it.
  3. Recursive Sorting: Recursively apply the above steps to the sub-arrays formed by partitioning.

After partitioning, the pivot is in its correct position, and the process is applied recursively to the sub-arrays.

Detailed Walkthrough

Let's understand how the partition function operates:

  • Choosing the Pivot: We can select the pivot as the last element of the array.
  • Partitioning: We maintain two pointers. One pointer to track elements less than the pivot and another for the current element being compared. If the current element is less than the pivot, we swap it with the element at the pointer tracking smaller elements.

The function partition arranges the array such that every element less than the pivot is moved before it, and all greater elements come after it. Then, we place the pivot in its correct position.

Quick Sort Algorithm Implementation

Here’s a step-by-step code representation of the Quick Sort algorithm in C++:

#include <iostream>
using namespace std;

// 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
// and places all smaller elements to the left of pivot and all greater elements to the 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 the current element is smaller than or equal to 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) {
        // Partitioning index, arr[pi] is now at the right place 
        int pi = partition(arr, low, high);

        // Separately sort elements before and after partition
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    )
}

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

// Main driver code
int main() (
    int arr[] = {10, 7, 8, 9, 1, 5);
    int n = sizeof(arr) / sizeof(arr[0]);
    quickSort(arr, 0, n - 1);
    cout << "Sorted array: \n";
    printArray(arr, n);
    return 0;
}

Time Complexity

The time complexity of the Quick Sort algorithm depends on the choice of the pivot:

  • Best Case: O(n log n), when the pivot divides the array into two equal halves.
  • Average Case: O(n log n), often achieved with a random pivot choice.
  • Worst Case: O(n^2), when the pivot is the smallest or largest element resulting in a highly unbalanced partition.

Key Points

  1. Quick Sort is efficient for large datasets.
  2. It’s an in-place sort (i.e., it requires only a small, constant amount of extra storage space).
  3. Generally performs better than Merge Sort in practice.

Keywords

  • Quick Sort
  • Pivot
  • Partitioning
  • Recursive Sorting
  • Time Complexity

FAQ

Q1: What is the basic idea behind Quick Sort? A1: The basic idea of Quick Sort is to select a pivot element and partition the array such that elements less than the pivot are on the left and elements greater than the pivot are on the right. This process is then recursively applied to the sub-arrays.

Q2: How do you choose the pivot in Quick Sort? A2: The pivot can be any element from the array. Common choices include the first element, the middle element, the last element, or a random element.

Q3: What is the time complexity of Quick Sort? A3: The time complexity of Quick Sort is O(n log n) in the best and average cases, and O(n^2) in the worst case.

Q4: Is Quick Sort an in-place algorithm? A4: Yes, Quick Sort is an in-place sorting algorithm as it requires a very small, constant amount of extra storage space.

Q5: How does Quick Sort perform compared to other sorting algorithms like Merge Sort? A5: Quick Sort generally performs better than Merge Sort in practice due to its in-place nature and better cache performance. However, Merge Sort has a more predictable O(n log n) time complexity, whereas Quick Sort has a worst-case time complexity of O(n^2).