In Java, I\'m trying to implement an iterative(non-recursive) quicksort for a gi

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. From debugging process it seems my quicksort is using the index's of the numbers and not the elements themselvs while sorting. Any advice on my code would be appreciated! There is also test code provided.

//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

import org.junit.Assert;
import org.junit.Test;
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;
        int pivot = array[lowerIndex+(higherIndex-lowerIndex)/2];
        while (i <= j) {
            while (array[i] < pivot) {
                i++;
            }
            while (array[j] > pivot) {
                j--;
            }
            if (i <= j) {
                exchangeNumbers(i, j);
                i++;
                j--;
            }
        }
        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(" ");
        }
    }
}

Output:
2 2 12 20 24 45 53 56 56 75 99

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.