Thread: Why is my Quick Sort using Iteration not working properly?

I am currently trying to benchmark a Quick Sort algorithm using both Iteration and Recursion. My problem is with my output, my recursive function works properly and sorts the elements. My iterative function is not working properly though. Here are 2 sample output's and my code that I have. You will see that the iterative function works sometimes but not every time. How do I fix this problem?


Output #1


ITERATIVE SORT
464 10 775 896 997

464
10
775
896
997
array index out of bounds
The array was not sorted correctly:
464 at index 0 and 10 at index 1

ITERATIVE SORT
929 225 730 915 991

929
225
730
915
991
array index out of bounds
The array was not sorted correctly:
929 at index 0 and 225 at index 1

ITERATIVE SORT
292 94 382 474 495

292
94
382
474
495
array index out of bounds
The array was not sorted correctly:
292 at index 0 and 94 at index 1

ITERATIVE SORT
207 349 612 719 962


RECURSIVE SORT
207 349 612 719 962
ITERATIVE SORT
655 157 366 806 865

655
157
366
806
865
array index out of bounds
The array was not sorted correctly:
655 at index 0 and 157 at index 1
Data Set Size (n): 5
Iterative Selection Sort Results: Recursive Selection Sort Results:
Average Critical Operation Count: 0 Average Critical Operation Count: 1
Standard Deviation of Count: 0 Standard Deviation of Count: 2
Average Execution Time: 800 Average Execution Time: 160
Standard Deviation of Time: 1600 Standard Deviation of Time: 320



Output #2


ITERATIVE SORT
11 280 305 356 970


RECURSIVE SORT
11 280 305 356 970
ITERATIVE SORT
287 288 459 649 774


RECURSIVE SORT
287 288 459 649 774
ITERATIVE SORT
341 446 569 882 902


RECURSIVE SORT
341 446 569 882 902
ITERATIVE SORT
181 308 382 513 627


RECURSIVE SORT
181 308 382 513 627
ITERATIVE SORT
744 53 917 941 978

744
53
917
941
978
array index out of bounds
The array was not sorted correctly:
744 at index 0 and 53 at index 1
Data Set Size (n): 5
Iterative Selection Sort Results: Recursive Selection Sort Results:
Average Critical Operation Count: 0 Average Critical Operation Count: 10
Standard Deviation of Count: 0 Standard Deviation of Count: 7
Average Execution Time: 0 Average Execution Time: 1400
Standard Deviation of Time: 0 Standard Deviation of Time: 990



SortMain.java

public class SortMain {
 
    public static void main(String[] args) throws Exception {
        int[] sizes = {5};    //, 200, 300, 400, 500, 600, 700, 800, 900, 1000, 1500, 2000, 2500, 5000, 7500, 10000, 15000};
        new BenchmarkSorts(sizes);
 
    }
}

BenchmarkSorts.java

import java.util.*;
import java.util.stream.*;
 
public class BenchmarkSorts {
 
	private final int NUMBER_OF_RUNS = 5;
 
    private int[] array;
 
    private int iterativeCount = 0;
    private int recursiveCount = 0;
 
    private int iterativeIndex = 0;
    private int recursiveIndex = 0;
 
    private long iterativeTime, recursiveTime;
 
    private int [] iterativeCountLog = new int[NUMBER_OF_RUNS];
    private int [] recursiveCountLog = new int[NUMBER_OF_RUNS];
    private long [] iterativeTimeLog = new long[NUMBER_OF_RUNS];
    private long [] recursiveTimeLog = new long[NUMBER_OF_RUNS];
 
    private static QuickSort quickSort = new QuickSort();
 
	 public BenchmarkSorts(int[] sizes) {
		 // Creates benchmarks based on the input array size
	     IntStream.range(0, sizes.length).forEach(i -> new BenchmarkSorts(sizes[i]));
	 }
 
	 private BenchmarkSorts(int n) {
		 // Outer loop 50 times (NUMBER_OF_RUNS)
	     IntStream.range(0, NUMBER_OF_RUNS).forEach(i -> {
	    	 array = new int[n];
	    	 // Inner loop based on the array size (n)
	    	 IntStream.range(0, n).forEach(j -> {
	    		 Random random = new Random();
	    		 array[j] = random.nextInt(1000);
	    	 });
	    	 // Runs the sort and produces output if an UnsortedException is found
	    	 try {
	    		 runSorts();
	    	 } 
	    	 catch (UnsortedException e) {
	    		 System.out.println(e.getMessage());
	    	 }
	     });
	     displayReport(n);
	}
 
	private void runSorts() throws UnsortedException {
		// Runs iterative sort
        int returnCount = quickSort.getCount();
        long returnTime = quickSort.getTime();
        System.out.println("\nITERATIVE SORT");
        int[] newArray1 = quickSort.iterativeSort(array, 0, array.length -1);
        quickSort.printArr(newArray1, newArray1.length);
        System.out.println("\n");
        quickSort.checkSortedArray(newArray1);
        iterativeCount = iterativeCount + returnCount;
        iterativeTime = iterativeTime + returnTime;
        iterativeCountLog[iterativeIndex] = iterativeCount;
        iterativeTimeLog[iterativeIndex] = iterativeTime;
        iterativeIndex++;
 
        // Runs recursive sort
        System.out.println("\nRECURSIVE SORT");
        int[] newArray2 = quickSort.recursiveSort(array, 0, array.length-1);
        quickSort.printArr(newArray2, newArray2.length);
        quickSort.checkSortedArray(newArray2);
        returnCount = quickSort.getCount();
        returnTime = quickSort.getTime();
        recursiveCount = recursiveCount + returnCount;
        recursiveTime = recursiveTime + returnTime;
        recursiveCountLog[recursiveIndex] = recursiveCount;
        recursiveTimeLog[recursiveIndex] = recursiveTime;
        recursiveIndex++;
	}
 
	private void displayReport(int arraySize) {
 
        // Sets local variables
        double iterativeAverageCount = 0;
        double iterativeAverageTime = 0;
        double recursiveAverageCount = 0;
        double recursiveAverageTime = 0;
        double iterativeVarianceCount = 0;
        double iterativeVarianceTime = 0;
        double recursiveVarianceCount = 0;
        double recursiveVarianceTime = 0;
        double iterativeSDCount = 0;
        double iterativeSDTime = 0;
        double recursiveSDCount = 0;
        double recursiveSDTime = 0;
 
        // Calculates averages
        for (int i = 0; i < NUMBER_OF_RUNS; i++) {
        	iterativeAverageCount += iterativeCountLog[i];
        	iterativeAverageTime += iterativeTimeLog[i];
        	recursiveAverageCount += recursiveCountLog[i];
        	recursiveAverageTime += recursiveTimeLog[i];
        }
 
        iterativeAverageCount = iterativeAverageCount / arraySize;
        iterativeAverageTime = iterativeAverageTime / arraySize;
        recursiveAverageCount = recursiveAverageCount / arraySize;
        recursiveAverageTime = recursiveAverageTime / arraySize;
 
        // Calculates standard deviations
        for (int i = 0; i < NUMBER_OF_RUNS; i++) {
            iterativeVarianceCount += Math.pow(iterativeAverageCount - iterativeCountLog[i], 2);
            iterativeVarianceTime += Math.pow(iterativeAverageTime - iterativeTimeLog[i], 2);
            recursiveVarianceCount += Math.pow(recursiveAverageCount - recursiveCountLog[i], 2);
            recursiveVarianceTime += Math.pow(recursiveAverageTime - recursiveTimeLog[i], 2);
        }
 
        iterativeVarianceCount = iterativeVarianceCount / arraySize;
        iterativeVarianceTime = iterativeVarianceTime / arraySize;
        recursiveVarianceCount = recursiveVarianceCount / arraySize;
        recursiveVarianceTime = recursiveVarianceTime / arraySize;
 
        iterativeSDCount = Math.sqrt(iterativeVarianceCount);
        iterativeSDTime = Math.sqrt(iterativeVarianceTime);
        recursiveSDCount = Math.sqrt(recursiveVarianceCount);
        recursiveSDTime = Math.sqrt(recursiveVarianceTime);
 
        // Produces output
        System.out.println("Data Set Size (n): " + arraySize +
        		"\n\tIterative Selection Sort Results: \t\t\t\t\tRecursive Selection Sort Results:" +
        		"\n\tAverage Critical Operation Count: " + Math.round(iterativeAverageCount) +
        		"\t\t\tAverage Critical Operation Count: " + Math.round(recursiveAverageCount) +
        		"\n\tStandard Deviation of Count: " + Math.round(iterativeSDCount) +
        		"\t\t\t\t\tStandard Deviation of Count: " + Math.round(recursiveSDCount) +
        		"\n\tAverage Execution Time: " + Math.round(iterativeAverageTime) +
        		"\t\t\t\t\t\tAverage Execution Time: " + Math.round(recursiveAverageTime) +
        		"\n\tStandard Deviation of Time: " + Math.round(iterativeSDTime) +
        		"\t\t\t\t\t\tStandard Deviation of Time: " + Math.round(recursiveSDTime));
	}
}

QuickSort.java

public class QuickSort implements SortInterface {  
 
    private static int count = 0;
    private static long timeStart = 0;
    private static long timeEnd = 0;
 
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
	public static int partition(int[] array, int low, int high) {
 
		int pivot = array[high];
		int i = (low - 1);
 
		for (int j = low; j <= high - 1; j++) {
			if(array[j] <= pivot) {
				i++;
				swap(array, i, j);
			}
		}
		swap(array, i + 1, high);
		return i + 1;	    
    }
 
	//  function to recursively sort the list
	public int[] recursiveSort(int[] array, int low, int high) throws UnsortedException {
		count++;
    	timeStart = System.nanoTime();
    	int i = partition(array, low, high);
 
    	if(low < i - 1) {
    		recursiveSort(array, low, i - 1);
    	}
 
    	if(high > i) {
    		recursiveSort(array, i, high);
    	}
	    timeEnd = System.nanoTime();
	    return array;
    }
 
	public int[] iterativeSort(int[] array, int low, int high) throws UnsortedException {
		count++;
    	timeStart = System.nanoTime();
		int stack[] = new int[high - 1 + 1];
		int top = -1;
 
		stack[++top] = low;
		stack[++top] = high;
 
		while (top >= 0) {
			high = stack[top--];
			low = stack[top--];
 
			int pivot = partition(array, low, high);
 
			if(pivot - 1 > 1) {
				stack[++top] = 1;
				stack[++top] = pivot - 1;
			}
 
			if(pivot + 1 < high) {
				stack[++top] = pivot + 1;
				stack[++top] = high;
			}
		}
	    timeEnd = System.nanoTime();
	    return array;
    }
 
    public int[] printArr(int array[], int n)
    {
        int i;
        for (i = 0; i < n; ++i) {
            System.out.print(array[i] + " ");
        }
        return array;
    }
 
    public int getCount() {
        int result = count;
        count = 0;
        return result;
    }
 
    public long getTime() {
        long time = timeEnd - timeStart;
        timeEnd = 0;
        timeStart = 0;
        return time;
    }
 
    public void checkSortedArray(int[] list) throws UnsortedException {
    	if(list == null || list.length <= 1) {
    		System.out.println("Array is sorted: null or 1 element");
    	}
 
        for (int i = 0; i < list.length - 1; i++) {
            if (list[i] > list[i + 1]) {
            	try {
            		for (int j = 0; i < list.length - 1; j++) {
            			System.out.println(" " + list[j]);           			
            		}
            		System.out.println("array is sorted");
            	}
            	catch(ArrayIndexOutOfBoundsException e) {
                	System.out.println("array index out of bounds");
                }
                throw new UnsortedException("The array was not sorted correctly: \n" +
                        list[i] + " at index " + i + " and " + list[i + 1] + " at index " + (i + 1));
            }
        }
    }
	@Override
	public int[] iterativeSort(int[] array) throws UnsortedException {
		// TODO Auto-generated method stub
		return null;
	}
	@Override
	public int[] recursiveSort(int[] array) throws UnsortedException {
		// TODO Auto-generated method stub
		return null;
	}
}

SortInterface.java

public interface SortInterface {
 
    int[] iterativeSort(int[] array) throws UnsortedException;
    int[] recursiveSort(int[] array) throws UnsortedException;
 
    int getCount();
    long getTime();
}

UnsortedException.java

public class UnsortedException extends Exception {
 
	private static final long serialVersionUID = 1L;
 
	public UnsortedException(String message) {
        super(message);
    }
}

Originally Posted by Norm

What statement has the error?
What is the value of the invalid index?

When the array isn't sorted from [lowest,...,highest] in BenchmarkSorts.java runSorts() method is where the error happens.

private void runSorts() throws UnsortedException {
	// Runs iterative sort
        int returnCount = quickSort.getCount();
        long returnTime = quickSort.getTime();
        System.out.println("\nITERATIVE SORT");
        int[] newArray1 = quickSort.iterativeSort(array, 0, array.length -1);
        quickSort.printArr(newArray1, newArray1.length);
        System.out.println("\n");
        quickSort.checkSortedArray(newArray1);   //<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<right here
        iterativeCount = iterativeCount + returnCount;
        iterativeTime = iterativeTime + returnTime;
        iterativeCountLog[iterativeIndex] = iterativeCount;
        iterativeTimeLog[iterativeIndex] = iterativeTime;
        iterativeIndex++;
 
        // Runs recursive sort
        System.out.println("\nRECURSIVE SORT");
        int[] newArray2 = quickSort.recursiveSort(array, 0, array.length-1);
        quickSort.printArr(newArray2, newArray2.length);
        quickSort.checkSortedArray(newArray2);
        returnCount = quickSort.getCount();
        returnTime = quickSort.getTime();
        recursiveCount = recursiveCount + returnCount;
        recursiveTime = recursiveTime + returnTime;
        recursiveCountLog[recursiveIndex] = recursiveCount;
        recursiveTimeLog[recursiveIndex] = recursiveTime;
        recursiveIndex++;
	}

The value changes every iteration because its a new array of 5 random integers. Sometimes the Iteration works and uses quick sort algorithm effectively other times it never moves the element at index[0] and thus I get this output:

you'll notice its always the first element at index[0] and the second element at [1] that always throw the array index out of bounds exception. Is it my iterative function that's wrong? if so, why does it work sometimes and not others?


ITERATIVE SORT
744 53 917 941 978

744
53
917
941
978
array index out of bounds
The array was not sorted correctly:
744 at index 0 and 53 at index 1

When the iterative function wants to work seems totally random, I don't see a pattern. If it was every other call that the function didn't work I would assume its in the while loop, but the program exceptions can range anywhere from 0(none)-5(max).

I have run the Iterative function by itself in a separate program and it works every time with the supplied values I have given it. That eliminates iterativeSort() method from the possible errors list.

The original (randomly generated) array and the somewhat sorted array returned from iterativeSort() method have identical elements every time so I know there's no problem with the pass-by-value.


Output 1


ORIGINAL ARRAY
291 982 192 223 531
ITERATIVE SORT
291 192 223 531 982 <<<<<<<<<<<<<<<<<<<<<<<didn't work

291
192
223
531
982
array index out of bounds
The array was not sorted correctly:
291 at index 0 and 192 at index 1


ORIGINAL ARRAY
539 682 3 245 717
ITERATIVE SORT
539 3 245 682 717 <<<<<<<<<<<<<<<<<<<<<<<didn't work

539
3
245
682
717
array index out of bounds
The array was not sorted correctly:
539 at index 0 and 3 at index 1


ORIGINAL ARRAY
227 203 679 294 846
ITERATIVE SORT
227 203 294 679 846 <<<<<<<<<<<<<<<<<<<<<<<didn't work

227
203
294
679
846
array index out of bounds
The array was not sorted correctly:
227 at index 0 and 203 at index 1


ORIGINAL ARRAY
743 365 940 157 155
ITERATIVE SORT
155 157 365 743 940 <<<<<<<<<<<<<<<<<<<<<<<WORKED



ORIGINAL ARRAY
739 192 85 68 419
ITERATIVE SORT
192 68 85 419 739 <<<<<<<<<<<<<<<<<<<<<<<didn't work

192
68
85
419
739
array index out of bounds
The array was not sorted correctly:
192 at index 0 and 68 at index 1



Output 2


ORIGINAL ARRAY
870 117 382 769 28
ITERATIVE SORT
28 117 382 769 870 <<<<<<<<<<<<<<<<<<<<<<<WORKED



ORIGINAL ARRAY
639 815 434 929 94
ITERATIVE SORT
94 434 639 815 929 <<<<<<<<<<<<<<<<<<<<<<<WORKED



ORIGINAL ARRAY
83 764 513 869 865
ITERATIVE SORT
83 513 764 865 869 <<<<<<<<<<<<<<<<<<<<<<<WORKED



ORIGINAL ARRAY
439 942 805 87 776
ITERATIVE SORT
439 87 776 805 942 <<<<<<<<<<<<<<<<<<<<<<<didn't work

439
87
776
805
942
array index out of bounds
The array was not sorted correctly:
439 at index 0 and 87 at index 1


ORIGINAL ARRAY
340 226 296 924 317
ITERATIVE SORT
226 296 317 340 924 <<<<<<<<<<<<<<<<<<<<<<<WORKED



IterativeQuickSort.java **separated function to clarify the code works as it should**

// Java implementation of iterative quick sort
class IterativeQuickSort {
    void swap(int arr[], int i, int j)
    {
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
 
    /* This function is same in both iterative and
       recursive*/
    int partition(int arr[], int l, int h)
    {
        int x = arr[h];
        int i = (l - 1);
 
        for (int j = l; j <= h - 1; j++) {
            if (arr[j] <= x) {
                i++;
                // swap arr[i] and arr[j]
                swap(arr, i, j);
            }
        }
        // swap arr[i+1] and arr[h]
        swap(arr, i + 1, h);
        return (i + 1);
    }
 
    // Sorts arr[l..h] using iterative QuickSort
    void QuickSort(int arr[], int l, int h)
    {
        // create auxiliary stack
        int stack[] = new int[h - l + 1];
 
        // initialize top of stack
        int top = -1;
 
        // push initial values in the stack
        stack[++top] = l;
        stack[++top] = h;
 
        // keep popping elements until stack is not empty
        while (top >= 0) {
            // pop h and l
            h = stack[top--];
            l = stack[top--];
 
            // set pivot element at it's proper position
            int p = partition(arr, l, h);
 
            // If there are elements on left side of pivot,
            // then push left side to stack
            if (p - 1 > l) {
                stack[++top] = l;
                stack[++top] = p - 1;
            }
 
            // If there are elements on right side of pivot,
            // then push right side to stack
            if (p + 1 < h) {
                stack[++top] = p + 1;
                stack[++top] = h;
            }
        }
    }
 
    // A utility function to print contents of arr
    void printArr(int arr[], int n)
    {
        int i;
        for (i = 0; i < n; ++i)
            System.out.print(arr[i] + " ");
    }
 
    // Driver code to test above
    public static void main(String args[])
    {
        IterativeQuickSort ob = new IterativeQuickSort();
        int arr[] = { 4, 3, 5, 2, 1, 3, 2, 3 };
        ob.QuickSort(arr, 0, arr.length - 1);
        ob.printArr(arr, arr.length);
    }
}

--- Update ---

Originally Posted by Norm

Did you find where the error happens?
The marked statement does not use an index and would not throw an exception.

This is the output if I remove the try/catch for ArrayIndexOutOfBounds Exception from checkSortedArray() inside QuickSort.java

ORIGINAL ARRAY
913 121 747 276 828 
ITERATIVE SORT
121 276 747 828 913 
 
 
ORIGINAL ARRAY
453 196 877 906 883 
ITERATIVE SORT
453 196 877 883 906 
 
 453
 196
 877
 883
 906
 
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 5 out of bounds for length 5
	at QuickSort.checkSortedArray(QuickSort.java:101)
	at BenchmarkSorts.runSorts(BenchmarkSorts.java:61)
	at BenchmarkSorts.lambda$1(BenchmarkSorts.java:44)
	at java.base/java.util.stream.Streams$RangeIntSpliterator.forEachRemaining(Streams.java:104)
	at java.base/java.util.stream.IntPipeline$Head.forEach(IntPipeline.java:617)
	at BenchmarkSorts.<init>(BenchmarkSorts.java:33)
	at BenchmarkSorts.lambda$0(BenchmarkSorts.java:28)
	at java.base/java.util.stream.Streams$RangeIntSpliterator.forEachRemaining(Streams.java:104)
	at java.base/java.util.stream.IntPipeline$Head.forEach(IntPipeline.java:617)
	at BenchmarkSorts.<init>(BenchmarkSorts.java:28)
	at SortMain.main(SortMain.java:5)

checkSortedArray() method modified with **no caught exceptions

    public void checkSortedArray(int[] list) throws UnsortedException {
    	if(list == null || list.length <= 1) {
    		System.out.println("Array is sorted: null or 1 element");
    	}
 
        for (int i = 0; i < list.length - 1; i++) {
            if (list[i] > list[i + 1]) {
            	//try {
            		for (int j = 0; i < list.length - 1; j++) {
            			System.out.println(" " + list[j]);           			
            		}
            	//}
            	//catch(ArrayIndexOutOfBoundsException e) {
                	//System.out.println("array index out of bounds");
                //}
                throw new UnsortedException("The array was not sorted correctly: \n" +
                        list[i] + " at index " + i + " and " + list[i + 1] + " at index " + (i + 1));
            }
        }
    }

Originally Posted by Norm

Look at line 101 and see why the index on that line is past the end of the array.
Backtrack in the code to see how the index's value got past the end.

I solved the problem with thrown ArrayIndexOutOfBounds by setting the value of i = 1 in my for loop
EDIT: I now know by doing this my checkSortedArray() no longer detects unsorted arrays. Currently trying to figure out a different solution

    public void checkSortedArray(int[] list) throws UnsortedException {
    	if(list == null || list.length <= 1) {
    		System.out.println("Array is sorted: null or 1 element");
    	}
 
        for (int i = 1; i < list.length - 1; i++) {
            if (list[i] > list[i + 1]) {
            	try {
            		for (int j = 0; i < list.length - 1; j++) {
            			System.out.println(" " + list[j]);           			
            		}
            	}
            	catch(ArrayIndexOutOfBoundsException e) {
                	System.out.println("array index out of bounds");
                }
                throw new UnsortedException("The array was not sorted correctly: \n" +
                        list[i] + " at index " + i + " and " + list[i + 1] + " at index " + (i + 1));
            }
        }
    }

Originally Posted by Norm

I'm confused with why there is new and different code being posted. The latest post code doesn't look the same as the code in post#1

The different code **IterativeQuickSort.java** is a separate program that shows the Iterative Quick Sort Algorithm in my original post works.


Now that all syntax and runtime errors are taken care of. The other problem still remains, why is the program picking and choosing when to sort my array by use of iteration? This logical error is holding me back