In Java, I'm trying to implement an iterative(non-recursive) quicksort for a given generic array, and then present that array in order from least to greatest. I must use a stack implementation. From debugging process it seems my quicksort is using the index's of the numbers and not the elements themselvs while sorting. There is also test code provided.

Any advice on my code would be appreciated, please don't post some other random quicksort!

//MAIN CODE

import java.util.Stack;

public class QuickSort{

// provide non-recursive version of quick sort // hint: use stack to stored intermediate results public static > void sort(T[] a) { Stack stack = new Stack(); stack.push(0); stack.push(a.length); while (!stack.isEmpty()) { int lo = stack.pop(); int hi = stack.pop(); if (lo - hi < 2) { continue; } int j = lo + ((hi - lo) / 2); j = partition(a, lo, hi); stack.push(j + 1); stack.push(hi); stack.push(lo); stack.push(j); } return; }

// Partitions into a[lo..j-1], a[j], a[j+1..hi] private static > int partition(T[] a, int lo, int hi) { int i = lo, j = hi + 1; // left and right scan indices T v = a[lo]; // the pivot

while (true) { // Scan right, scan left, check for scan complete, and exchange while (SortUtils.isLessThan(a[++i], v)) {//++i is evaluated to i+1 if (i == hi) { break; } } while (SortUtils.isLessThan(v, a[--j])) {//--j is evaluated to j-1 if (j == lo) { break; } } if (i >= j) { break; }

SortUtils.swap(a, i, j); }

SortUtils.swap(a, lo, j); // Put v = a[j] into position return j; }

}

//TEST CODE

import org.junit.Assert; import org.junit.Test;

public class QuickSortTest {

@Test public void testSort1() { Integer[] a = {17}; Integer[] expected = {17}; QuickSort.sort(a); Assert.assertArrayEquals(expected, a); } @Test public void testSort2() { Integer[] a = {17, 5}; Integer[] expected = {5, 17}; QuickSort.sort(a); Assert.assertArrayEquals(expected, a); } @Test public void testSort3() { Integer[] a = {64, 18, 74, 89, 58, 17, 48, 44, 92, 88, 78, 80, 75, 25, 77, 18, 39, 95, 11, 2}; Integer[] expected = {2, 11, 17, 18, 18, 25, 39, 44, 48, 58, 64, 74, 75, 77, 78, 80, 88, 89, 92, 95}; QuickSort.sort(a); Assert.assertArrayEquals(expected, a); }

}