Iterative QuickSort Example in Java - without Recursion

The quicksort algorithm is one of the important sorting algorithms. Similar to merge sort, quicksort also uses divide-and-conquer hence it's easy to implement a quicksort algorithm using recursion in Java, but it's slightly more difficult to write an iterative version of quicksort. That's why Interviewers are now asking to implement QuickSort without using recursion. The interview will start with something like writing a program to sort an array using a quicksort algorithm in Java and most likely you will come up with a recursive implementation of quicksort as shown here. As a  follow-up, the Interviewer will now ask you to code the same algorithm using Iteration.

If you remember, while solving binary tree problems without recursion e.g. pre-order traversal without recursion (here) and in-order traversal without recursion (here), we have used Stack to replace recursion. You can use the same technique here to write an iterative quicksort program in Java. The Stack actually mimics the recursion.

Before going for a programming/coding interview, It's absolutely necessary to do as much practice in data structure and algorithms as possible to take advantage of all the knowledge available. You can also join a comprehensive Data Structure and Algorithms course like Data Structures and Algorithms: Deep Dive Using Java on Udemy to fill the gaps in your understanding.

Iterative Quicksort Algorithm

I learned about quicksort in my engineering classes, one of the few algorithms which I managed to understand then. Since it's a divide-and-conquer algorithm, you choose a pivot and divide the array.

Unlike merge sort, which is also a divide-and-conquer algorithm and where all-important work happens on combine steps, In quicksort, the real work happens in the divide step and the combining step does nothing important.

Btw, the working of the algorithm will remain the same whether you implement an iterative solution or a recursion solution. In an iterative solution, we'll use Stack instead of Recursion. 

Here are the steps to implement iterative quicksort in Java:

• Push the range (0...n) into the Stack
• Partition the given array with a pivot
• Pop the top element.
• Push the partitions ( index range ) into a stack if the range has more than one element
• Do the above 3 steps, till the stack, is empty

You might know that even though writing recursive algorithms are easy they are always slower than their Iterative counterpart. So, when the Interviewer will ask you to choose a method in terms of time complexity where memory is not a concern, which version will you choose?

Well, both recursive and iterative quicksorts are O(N log N) average case and O(n^2) in the worst case but the recursive version is shorter and clearer. Iterative is faster and makes you simulate the recursion call stack.

Btw, if you want to understand more about what does recursion has to do with the stack? and why does quicksort run in O(n log n) time in the average case? I suggest reading Grokking Algorithms, a rare algorithm book that is easy to understand with real-world examples. I just bought a copy of this book and even though I know all those algorithms, I find it quite readable and gain a new perspective. So, if you are struggling with the algorithms, this is the book you should read now.

QuickSort example in Java without recursion.

Here is our sample Java program to implement Quicksort using for loop and stack, without using recursion. This is also known as the iterative quicksort algorithm.

import java.util.Arrays;
import java.util.Scanner;
import java.util.Stack;

/**
 * Java Program to implement Iterative QuickSort Algorithm, without recursion.
 *
 * @author WINDOWS 8
 */
public class Sorting {

    public static void main(String args[]) {

        int[] unsorted = {34, 32, 43, 12, 11, 32, 22, 21, 32};
        System.out.println("Unsorted array : " + Arrays.toString(unsorted));

        iterativeQsort(unsorted);
        System.out.println("Sorted array : " + Arrays.toString(unsorted));
    }


    /*
     * iterative implementation of quicksort sorting algorithm.
     */
    public static void iterativeQsort(int[] numbers) {
        Stack stack = new Stack();
        stack.push(0);
        stack.push(numbers.length);

        while (!stack.isEmpty()) {
            int end = stack.pop();
            int start = stack.pop();
            if (end - start < 2) {
                continue;
            }
            int p = start + ((end - start) / 2);
            p = partition(numbers, p, start, end);

            stack.push(p + 1);
            stack.push(end);

            stack.push(start);
            stack.push(p);

        }
    }

    /*
     * Utility method to partition the array into smaller array, and
     * comparing numbers to rearrange them as per quicksort algorithm.
     */
    private static int partition(int[] input, int position, int start, int end) {
        int l = start;
        int h = end - 2;
        int piv = input[position];
        swap(input, position, end - 1);

        while (l < h) {
            if (input[l] < piv) {
                l++;
            } else if (input[h] >= piv) {
                h--;
            } else {
                swap(input, l, h);
            }
        }
        int idx = h;
        if (input[h] < piv) {
            idx++;
        }
        swap(input, end - 1, idx);
        return idx;
    }

    /**
     * Utility method to swap two numbers in given array
     *
     * @param arr - array on which swap will happen
     * @param i
     * @param j
     */
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

}

Output:
Unsorted array : [34, 32, 43, 12, 11, 32, 22, 21, 32]
Sorted array : [11, 12, 21, 22, 32, 32, 32, 34, 43]

That's all about how to implement quicksort in Java without recursion. Just remember, when you use for loop and stack to implement quicksort, it's known as iterative implementation and when you call the method itself, it's known as recursive implementation. 

The recursive solution of quicksort is easier to write and understand but the iterative solution is much faster. Though average and worst-case time complexity of both recursive and iterative quicksorts are O(N log N) average case and O(n^2).

Btw, if you want to remember or review the time complexity of different sorting algorithms e.g. quicksort, merge sort, insertion sort, radix sort, shell sort, or bubble sort, here is a nice slide you can print and use:

If you want to learn more about quicksort or other sorting algorithms, I suggest you either read tried and tested Introduction to Algorithms by Thomas H. Cormen, which myself and several other programmers have read to learn the fundamentals of data structure and algorithms. 

Alternatively, you can also choose the newer, but more interesting book Grokking Algorithms by Aditya Bhargava, who explains algorithms with lots of real-world examples and diagrams. If you are a beginner, I would suggest going for Grokking Algorithms.

Other data structure and algorithm articles you may like

• How to implement an insertion sort algorithm in Java? (answer)
• Write a program to implement bubble sort in Java? (solution)
• How to implement a binary search algorithm in Java? (solution)
• How to implement the sieve of the Eratosthenes algorithm in Java? (solution)
• How to implement pre-order traversal of a binary tree in Java? (solution)
• How to implement in-order traversal in Java? (solution)
• How to print all leaf nodes of a binary tree in Java? (solution)
• How to implement a binary search tree in Java? (solution)
• 10 Free Data STructure and algorithm courses? (free courses)
• 21 String Programming Interview Questions in Java? (questions)

Thanks for reading this article so far. If you like my implementation and explanation of the iterative Quicksort algorithm in Java then please share with your friends and colleagues. If you have any questions or feedback please drop a note.