jeudi 26 août 2021

Randomized QuickSort IndexOutOfBounds exception

this is the QuickSort Randomized that I've come up with, but it constantly throws out IndexOutOfBounds exception. Could I have some help with it? Thanks!

import java.util.Random;

public class QuickSort {

    void quickSort(int[] A, int start, int end) { // Initially: start = 0, end = n-1
        while (start < end) {
            int iOfPartition = randomisedPartition(A, start, end);
            if (iOfPartition - start < end - iOfPartition) {
                quickSort(A, start, iOfPartition - 1);
                start = iOfPartition + 1;
            } else {
                quickSort(A, iOfPartition + 1, end);
                end = iOfPartition - 1;
            }
        }
    }

    int randomisedPartition(int[] A, int start, int end) {
        Random rng = new Random();
        int randomNum = rng.nextInt(end + 1 - start) + start;
        swap(A, A[randomNum], A[start]);
        return hoarePartition(A, start, end);
    }

    int hoarePartition(int[] A, int start, int end) {
        int pivot = A[start];
        int i = start;
        int j = end;
        while (i < j) {
            while (A[i] <= pivot && i < end) i++;
            while (A[j] > pivot && j > start) j--;
            if (i < j) swap(A, A[i], A[j]); 
        }
        swap(A, A[start], A[j]);
        return j; 
    }

    void swap(int[] A, int i, int j) {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }
}

I keep getting an arrayindexoutofbounds error.




Aucun commentaire:

Enregistrer un commentaire