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 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 quicksort algorithm in Java and most likely you will come up with a recursive implementation of quicksort as shown here. As a  follow-up, 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.


Iterative Quicksort Algorithm

I learned about quicksort in my engineering classes, one of the few algorithm 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 divide step and the combining step does nothing important.


Btw, the working of the algorithm will remain same whether you implement an iterative solution or a recursion solution. In 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 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 have 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 which 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.

Iterative QuickSort Example in Java - without Recursion



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 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:

iterative quicksort time and space complexity



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 fundamentals of data structure and algorithm. Alternatively, you can also choose the newer, but more interesting book Grokking Algorithms by Aditya Bhargava, who explains algorithms with lots of real world example 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 insertion sort algorithm in Java? (answer)
  • Write a program to implement bubble sort in Java? (solution)
  • How to implement binary search algorithm in Java? (solution)
  • How to implement sieve of 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 binary search tree in Java? (solution)

References
Quicksort Algorithm
Overview of quicksort by Khan Academy




1 comment :

Gordan12 said...

Can I ask why are you importing Scanner if you're not using it?(I am a beginner)

Post a Comment