Jun 27, 2016

Iterative Quick Sort in Java

Problem: - Quick Sort using Iterative approach.

Sample code for iterative quick sort:

import java.util.Stack;


public class HeapSortIterative {

 static int[] input2 = { 2, 23, 45, 67, 5, 27, 6, 7, 12, 21, 67, 89 };
 static int[] input3 = { 2, 23, 45, 67, 5, 27, 6, 7, 12, 21, 67, 89 };

 /**
  * Sorting of complexity O(nlogn)
  */
 public static void main(String[] args) {
  System.out.println("\n==========Iterative Quicksort============");
  int[] input1 = { 2, 23, 5, 27, 6, 7, 12, 21 };
  System.out.println("Before sorting");
  for (int i = 0; i < input1.length; i++) {
   System.out.print(input1[i] + " ");
  }
  iterativeQuicksort(input1, 0, input1.length - 1);
  System.out.println("\n\nAfter sorting");
  
  for (int i = 0; i < input1.length; i++) {
   System.out.print(input1[i] + " ");
  }
 }
 // iterative quick sort
 public static void iterativeQuicksort(int[] input, int low, int high) {
  Stack<Integer> stack = new Stack<Integer>();
  stack.push(low);
  stack.push(high);
  while (!stack.isEmpty()) {
   int h = stack.pop();
   int l = stack.pop();
   int partionIndex = partition(input, l, h, input[h]);
   if (partionIndex - 1 > l) {
    stack.push(l);
    stack.push(partionIndex - 1);
   }
   if (partionIndex + 1 < h) {
    stack.push(partionIndex + 1);
    stack.push(h);
   }
  }
 }

 private static int partition(int[] input, int low, int high, int pivot) {
  int left = low - 1;
  int right = high;
  while (true) {
   while (input[++left] < pivot && left < right)
    ;
   while (input[--right] > pivot && right > 0)
    ;
   if (left <= right)
    Util.swap(left, right, input);
   else
    break;
  }
  Util.swap(left, high, input);
  return left;
 }
}
class Util {
 @SuppressWarnings("unused")
 public static void swap(int i, int j, int[] arr) {
  int temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
 }
}
Sample output:-
C:\java-sample> javac HeapSortIterative.java
C:\java-sample> java HeapSortIterative

==========Iterative Quicksort============
Before sorting
2 23 5 27 6 7 12 21

After sorting
2 5 6 7 12 21 23 27


Location: Hyderabad, Telangana, India