Iterative Quick Sort Program with Explanation and Code

2025-11-19 iterative quick sort non recursive quick sort sorting algorithm stack based sorting data structures divide and conquer algorithm programs quicksort iteration python iterative quicksort c quicksort iterative javascript sorting php sorting program csharp iterative quick sort

Learn Iterative Quick Sort, a non-recursive version of the Quick Sort algorithm using an explicit stack. Includes full explanation, detailed steps, and complete code examples in Python, C, JavaScript, PHP, and C#. Ideal for students and interview preparation.

Program Explanation

What is Iterative Quick Sort?

Iterative Quick Sort is a non-recursive version of the Quick Sort algorithm. Instead of relying on the call stack for recursive partitioning, it uses an explicit stack to manage sub-array boundaries manually. This avoids recursion overhead and is helpful in environments with shallow recursion limits.

Steps to Solve

Initialize an auxiliary stack to store low and high indices.
Push the initial range (0 to n−1) onto the stack.
Pop a range from the stack and partition it using a pivot.
Push the left sub-array boundaries if elements exist.
Push the right sub-array boundaries if elements exist.
Repeat until the stack becomes empty.
Once all sub-arrays are processed, the array is fully sorted.

Key Points

Iterative Quick Sort eliminates recursion overhead.
Uses manual stack instead of system call stack.
Still follows divide-and-conquer principles.
Time Complexity (Average): O(n log n)
Worst-case Time Complexity: O(n²)
Space Complexity: O(log n) due to stack usage.
Suitable for large arrays where recursion depth is a concern.

Program Code


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 iterative_quick_sort(arr):
    stack = [(0, len(arr) - 1)]

    while stack:
        low, high = stack.pop()

        if low < high:
            pi = partition(arr, low, high)

            stack.append((low, pi - 1))
            stack.append((pi + 1, high))

arr = list(map(int, input("Enter numbers: ").split()))
iterative_quick_sort(arr)
print("Sorted array:", arr)


#include <stdio.h>

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

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 iterativeQuickSort(int arr[], int l, int h) {
    int stack[h - l + 1];
    int top = -1;

    stack[++top] = l;
    stack[++top] = h;

    while (top >= 0) {
        h = stack[top--];
        l = stack[top--];

        int p = partition(arr, l, h);

        if (p - 1 > l) {
            stack[++top] = l;
            stack[++top] = p - 1;
        }

        if (p + 1 < h) {
            stack[++top] = p + 1;
            stack[++top] = h;
        }
    }
}

int main() {
    int n;
    printf("Enter number of elements: ");
    scanf("%d", &n);

    int arr[n];
    printf("Enter numbers: ");
    for (int i = 0; i < n; i++) scanf("%d", &arr[i]);

    iterativeQuickSort(arr, 0, n - 1);

    printf("Sorted array: ");
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);

    return 0;
}


function partition(arr, low, high) {
  let pivot = arr[high];
  let i = low - 1;

  for (let j = low; j < high; j++) {
    if (arr[j] < pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }

  [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
  return i + 1;
}

function iterativeQuickSort(arr) {
  let stack = [[0, arr.length - 1]];

  while (stack.length) {
    let [low, high] = stack.pop();

    if (low < high) {
      let pi = partition(arr, low, high);

      stack.push([low, pi - 1]);
      stack.push([pi + 1, high]);
    }
  }
}

let arr = prompt("Enter numbers:").split(" ").map(Number);
iterativeQuickSort(arr);
console.log("Sorted array:", arr);


using System;

class Program {

    static 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++;
                (arr[i], arr[j]) = (arr[j], arr[i]);
            }
        }

        (arr[i + 1], arr[high]) = (arr[high], arr[i + 1]);
        return i + 1;
    }

    static void IterativeQuickSort(int[] arr) {
        int low = 0, high = arr.Length - 1;
        int[] stack = new int[arr.Length];
        int top = -1;

        stack[++top] = low;
        stack[++top] = high;

        while (top >= 0) {
            high = stack[top--];
            low = stack[top--];

            int p = Partition(arr, low, high);

            if (p - 1 > low) {
                stack[++top] = low;
                stack[++top] = p - 1;
            }

            if (p + 1 < high) {
                stack[++top] = p + 1;
                stack[++top] = high;
            }
        }
    }

    static void Main() {
        Console.Write("Enter numbers: ");
        int[] arr = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);

        IterativeQuickSort(arr);

        Console.Write("Sorted array: ");
        foreach (int num in arr)
            Console.Write(num + " ");
    }
}


<?php

function partitionFunc(&$arr, $low, $high) {
    $pivot = $arr[$high];
    $i = $low - 1;

    for ($j = $low; $j < $high; $j++) {
        if ($arr[$j] < $pivot) {
            $i++;
            [$arr[$i], $arr[$j]] = [$arr[$j], $arr[$i]];
        }
    }

    [$arr[$i + 1], $arr[$high]] = [$arr[$high], $arr[$i + 1]];
    return $i + 1;
}

function iterativeQuickSort(&$arr) {
    $stack = [[0, count($arr) - 1]];

    while (!empty($stack)) {
        [$low, $high] = array_pop($stack);

        if ($low < $high) {
            $pi = partitionFunc($arr, $low, $high);

            array_push($stack, [$low, $pi - 1]);
            array_push($stack, [$pi + 1, $high]);
        }
    }
}

$arr = array_map('intval', explode(" ", readline("Enter numbers: ")));
iterativeQuickSort($arr);

echo "Sorted array: " . implode(" ", $arr);

?>