In Java, I\'m trying to implement an iterative(non-recursive) quicksort for a gi
ID: 3849903 • Letter: I
Question
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 <T extends Comparable<T>> void sort(T[] a) {
Stack<Integer> stack = new Stack<Integer>();
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 <T extends Comparable<T>> 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);
}
}
Explanation / Answer
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
package com.java2novice.sorting;
public class MyQuickSort {
private int array[];
private int length;
public void sort(int[] inputArr) {
if (inputArr == null || inputArr.length == 0) {
return;
}
this.array = inputArr;
length = inputArr.length;
quickSort(0, length - 1);
}
private void quickSort(int lowerIndex, int higherIndex) {
int i = lowerIndex;
int j = higherIndex;
// calculate pivot number, I am taking pivot as middle index number
int pivot = array[lowerIndex+(higherIndex-lowerIndex)/2];
// Divide into two arrays
while (i <= j) {
/**
* In each iteration, we will identify a number from left side which
* is greater then the pivot value, and also we will identify a number
* from right side which is less then the pivot value. Once the search
* is done, then we exchange both numbers.
*/
while (array[i] < pivot) {
i++;
}
while (array[j] > pivot) {
j--;
}
if (i <= j) {
exchangeNumbers(i, j);
//move index to next position on both sides
i++;
j--;
}
}
// call quickSort() method recursively
if (lowerIndex < j)
quickSort(lowerIndex, j);
if (i < higherIndex)
quickSort(i, higherIndex);
}
private void exchangeNumbers(int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
public static void main(String a[]){
MyQuickSort sorter = new MyQuickSort();
int[] input = {24,2,45,20,56,75,2,56,99,53,12};
sorter.sort(input);
for(int i:input){
System.out.print(i);
System.out.print(" ");
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.