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. 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 and in-order traversal without recursion, 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.

####

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:

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.

####

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;

}

}

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:

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.

If you remember, while solving binary tree problems without recursion e.g. pre-order traversal without recursion and in-order traversal without recursion, 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**

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

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.

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

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: