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


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 8 of 8

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

  1. #1
    Junior Member
    Join Date
    Sep 2021
    Posts
    11
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default 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. #2
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    On vacation
    Posts
    24,792
    Thanks
    57
    Thanked 2,687 Times in 2,637 Posts

    Default 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.
    If you don't understand my answer, don't ignore it, ask a question.

  3. #3
    Junior Member
    Join Date
    Sep 2021
    Posts
    11
    Thanks
    0
    Thanked 0 Times in 0 Posts

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

    Quote Originally Posted by Norm View Post
    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. #4
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    On vacation
    Posts
    24,792
    Thanks
    57
    Thanked 2,687 Times in 2,637 Posts

    Default 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.
    If you don't understand my answer, don't ignore it, ask a question.

  5. #5
    Junior Member
    Join Date
    Sep 2021
    Posts
    11
    Thanks
    0
    Thanked 0 Times in 0 Posts

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

    Quote Originally Posted by Norm View Post
    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));
                }
            }
        }

  6. #6
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    On vacation
    Posts
    24,792
    Thanks
    57
    Thanked 2,687 Times in 2,637 Posts

    Default 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
    If you don't understand my answer, don't ignore it, ask a question.

  7. #7
    Junior Member
    Join Date
    Sep 2021
    Posts
    11
    Thanks
    0
    Thanked 0 Times in 0 Posts

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

    Quote Originally Posted by Norm View Post
    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));
                }
            }
        }


    Quote Originally Posted by Norm View Post
    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. #8
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    On vacation
    Posts
    24,792
    Thanks
    57
    Thanked 2,687 Times in 2,637 Posts

    Default 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.
    If you don't understand my answer, don't ignore it, ask a question.

Similar Threads

  1. JDialog not working properly
    By agarta in forum What's Wrong With My Code?
    Replies: 4
    Last Post: March 24th, 2013, 10:46 PM
  2. Iterative quick sort using median of three values
    By omfgz in forum What's Wrong With My Code?
    Replies: 1
    Last Post: September 30th, 2012, 09:59 PM
  3. Java Quick Sort Optimization
    By javaNewb37 in forum What's Wrong With My Code?
    Replies: 1
    Last Post: December 4th, 2011, 07:32 AM
  4. [SOLVED] Quick JTable Column Sort Question
    By aussiemcgr in forum Java Theory & Questions
    Replies: 1
    Last Post: October 15th, 2010, 04:35 PM
  5. if else statement not working properly
    By tina G in forum Algorithms & Recursion
    Replies: 1
    Last Post: March 29th, 2010, 08:04 AM