The algorithm for the non-recursive (iterative) function of quicksort would be :
- 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
And the implementation in JAVA is as follows: (explanation is commented)
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]