Welcome to the Java Programming Forums

The professional, friendly Java community. 21,500 members and growing!

The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.

>> REGISTER NOW TO START POSTING

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

1. ## 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);
}
}```

2. ## Re: Why is my Quick Sort using Iteration not working properly?

array index out of bounds
What statement has the error?
What is the value of the invalid index?

Some suggestions for testing:
Remove/ comment out code that is not being tested
use Arrays class's toString to print out the contents of the array

Use a fixed set of arrays for sort tests, not randomly generated numbers.

3. ## Re: Why is my Quick Sort using Iteration not working properly?

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

4. ## Re: Why is my Quick Sort using Iteration not working properly?

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

other times it never moves the element at index[0] and thus I get this output:
How are you trying to debug the code?
Change the code to use the values given: 744 53 917 941 978
then trace the execution to see why the first element is not moved.

5. ## Re: Why is my Quick Sort using Iteration not working properly?

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 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 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));
}
}
}```

6. ## Re: Why is my Quick Sort using Iteration not working properly?

Take one of the arrays that was not sorted correctly and hardcode it in the program for testing.
Then trace the logic flow to see where the code is not working correctly.

java.lang.ArrayIndexOutOfBoundsException: Index 5 out of bounds for length 5
at QuickSort.checkSortedArray(QuickSort.java:101)
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.

the code works as it should
If you have working code, why not use that?

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

7. ## Re: Why is my Quick Sort using Iteration not working properly?

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

8. ## Re: Why is my Quick Sort using Iteration not working properly?

by setting the value of i = 1
That means the code is not looking at the first element in the array. It was the first element that was out of order.
That is NOT the solution to the java.lang.ArrayIndexOutOfBoundsException: problem.

At what statement does the exception happen? Why does the array index at that line go past the end of the array? Where does the code test that the index is not past the end of the array?

why is the program picking and choosing when to sort my array by use of iteration?
Where does the program make that decision? I do not see any comments in the code that discusses making that decision.

a separate program that shows the Iterative Quick Sort Algorithm in my original post works.
No. That is new and different code. It says nothing about why the code in the original post does not work.