Implementing Iterative Quick Sort in C++

Introduction:

Sorting algorithms are fundamental in computer science, playing a crucial role in various applications from databases to search algorithms. Among the myriad of sorting techniques, Quick Sort stands out for its efficiency and simplicity. In this article, we’ll delve into implementing Quick Sort iteratively in C++, a versatile and powerful programming language.

What is Quick Sort?

Quick Sort, devised by Tony Hoare in 1959, is a highly efficient sorting algorithm based on the divide-and-conquer strategy. It works by selecting a ‘pivot’ element from the array and partitioning the other elements into two sub-arrays according to whether they are less than or greater than the pivot. The process is recursively applied to the sub-arrays until the entire array is sorted.

Iterative Quick Sort in C++:

Traditionally, Quick Sort is implemented using recursion. However, recursion comes with its overhead, especially for large datasets, due to function call overhead and stack space usage. By implementing Quick Sort iteratively, we can overcome these limitations while maintaining its efficiency.

#include <iostream>
#include <stack>
using namespace std;

// Function to swap two elements
void swap(int &a, int &b) {
    int temp = a;
    a = b;
    b = temp;
}

// Partition function to partition the array
int partition(int arr[], int low, int high) {
    int pivot = arr[high]; // Pivot element
    int i = low - 1; // Index of smaller element

    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);
}

// Iterative Quick Sort function
void iterativeQuickSort(int arr[], int low, int high) {
    stack<int> stack; // Create a stack for storing sub-array indices
    stack.push(low);
    stack.push(high);

    while (!stack.empty()) {
        high = stack.top();
        stack.pop();
        low = stack.top();
        stack.pop();

        int pivot = partition(arr, low, high);

        if (pivot - 1 > low) {
            stack.push(low);
            stack.push(pivot - 1);
        }

        if (pivot + 1 < high) {
            stack.push(pivot + 1);
            stack.push(high);
        }
    }
}

// Function to print an 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[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    iterativeQuickSort(arr, 0, n - 1);
    cout << "Sorted array: \n";
    printArray(arr, n);
    return 0;
}

Iterative Quick Sort offers a compelling alternative to the traditional recursive approach, especially in scenarios where stack space is a concern. By harnessing the power of iteration, we can achieve efficient sorting of arrays in C++ without sacrificing performance. Experimenting with different implementations and understanding their trade-offs equips us with valuable insights into algorithm design and optimization.

Iterative Quicksort Algorithm

1. Choose a Pivot: Select a pivot element from the array. This pivot can be any element, typically chosen as the last element in the array.
2. Partitioning: Rearrange the array elements in such a way that all elements smaller than the pivot are placed before it, and all elements greater than the pivot are placed after it. After this operation, the pivot is in its final sorted position.
3. Divide and Conquer: Recursively apply the above steps to the sub-arrays formed by the partitioning process. That is, repeat the partitioning step on the sub-arrays to sort them.
4. Iteration: Instead of using recursion, we’ll use a stack data structure to keep track of the sub-arrays that need to be sorted. This allows us to simulate the function call stack used in the recursive version of Quick Sort.