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
0 comments:
Post a Comment