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