C++ • SORTING ALGORITHM Non-Recursive Quick Sort

C++ • SORTING ALGORITHM

Non-Recursive Quick Sort

ALGORITHM

Iterative Quick Sort

TIME COMPLEXITY

O(n log n)

SPACE COMPLEXITY

O(n)

ORDER

Ascending

C++ Implementation

iterative_quick_sort.cpp

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

class ArraySort
{
    int n;
    int a[100];

    // Partition function to place pivot at correct position
    int partition(int low, int high)
    {
        int pivot = a[high];
        int i = (low - 1);

        for (int j = low; j <= high - 1; j++)
        {
            if (a[j] < pivot)
            {
                i++;
                swap(a[i], a[j]);
            }
        }
        swap(a[i + 1], a[high]);
        return (i + 1);
    }

public:

    // Constructor
    ArraySort()
    {
        n = 0;
    }

    // Input function
    void input()
    {
        cout << "Enter length of array: ";
        cin >> n;

        cout << "Enter array elements: ";

        for(int i = 0; i < n; i++)
        {
            cin >> a[i];
        }
    }

    // Non-Recursive (Iterative) Quick Sort function using an explicit stack
    void quickSort()
    {
        int stack[100];
        int top = -1;

        // Push initial values of low and high to stack
        stack[++top] = 0;
        stack[++top] = n - 1;

        // Pop from stack while it is not empty
        while (top >= 0)
        {
            int high = stack[top--];
            int low = stack[top--];

            // Set pivot element at its correct position in sorted array
            int pi = partition(low, high);

            // If there are elements on left side of pivot, then push left side to stack
            if (pi - 1 > low)
            {
                stack[++top] = low;
                stack[++top] = pi - 1;
            }

            // If there are elements on right side of pivot, then push right side to stack
            if (pi + 1 < high)
            {
                stack[++top] = pi + 1;
                stack[++top] = high;
            }
        }
    }

    // Output function
    void output()
    {
        cout << "Sorted Array: ";

        for(int i = 0; i < n; i++)
        {
            cout << a[i] << " ";
        }
    }
};

int main()
{
    ArraySort obj;

    obj.input();
    obj.quickSort();
    obj.output();

    return 0;
}

Sample Input

Enter length of array: 5
Enter array elements:
5 3 4 1 2

Output

Sorted Array:
1 2 3 4 5

Line-by-Line Explanation

Code

Meaning

#include <iostream>

Includes standard input/output stream functions.

class ArraySort

Creates a class named ArraySort containing the array and sorting methods.

int n;

Stores the total number of elements in the array.

int a[100];

Declares an integer array capable of holding up to 100 elements.

int partition(int low, int high)

Picks a pivot and rearranges the array so smaller elements go left and larger elements go right.

ArraySort()

Class constructor that initializes object properties when instantiated.

n = 0;

Initializes the array size variable to zero.

void input()

Reads the array size and elements from the user.

int stack[100]; top = -1;

Simulates the function call stack manually using an integer array.

stack[++top] = ...

Pushes the starting and ending indices (0 and n-1) onto the explicit stack.

while (top >= 0)

Loops as long as there are sub-arrays left to be processed in the stack.

void output()

Displays the final sorted array to the console.

ArraySort obj;

Instantiates the ArraySort object and triggers the constructor.

return 0;

Signals successful program execution.

How non-recursive quick sort works: Instead of using the compiler's function call stack (recursion), this approach uses an explicit auxiliary array/stack to store the lower and upper bounds of sub-arrays. It repeatedly pops a sub-range, partitions it around a pivot, and pushes the resulting left and right sub-ranges back onto the stack until all parts are sorted.