import java.util.Random;
public class Quicksort {
private int partition(int arr[], int first, int last) {
int pivot = arr[last]; //Using last element as pivot
int i = (first-1);//index of smaller element
for (int j = first; j < last; j++) {
//if current element is smaller than or equal to pivot
//then swap the elements
if (arr[j] <= pivot) {
i++;
//swapping occurs here
//make a temp variable to the first element
//swap arr[j] and arr[i]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
//i++;
}
}
int temp = arr[i+1];
arr[i+1] = arr[last];
arr[last] = temp;
return i+1;
}
private void quickSort(int arr[], int first, int last) {
if (first < last) {
int pivindex = partition(arr, first, last);
quickSort(arr, first, pivindex-1);
quickSort(arr, pivindex+1, last);
}
}
public void sort(int[] arr) {
quickSort(arr, 0, arr.length - 1);
}
public static int[] getRandoms(int count) {
return new Random().ints().limit(count).toArray();
}
public static void main(String[] args) {
Quicksort fix = new Quicksort();
int[] randoms = getRandoms(40000);
double startTime = System.currentTimeMillis();
fix.sort(randoms);
double endTime = System.currentTimeMillis();
System.out.println("Performance Time on Random Data:" + (endTime - startTime));
//Benchmarking quicksort on already sorted data
startTime = System.currentTimeMillis();
fix.sort(randoms);
endTime = System.currentTimeMillis();
System.out.println("Performance Time on Sorted Data:" + (endTime - startTime));
}
}
Я не совсем уверен, почему я получаю Stackoverflowerror.Код работает нормально, когда я сортирую только один раз, однако, если я пытаюсь отсортировать одни и те же данные дважды, именно тогда я получаю сообщение об ошибке.
Я понимаю, что Stackoverflowerror возникает из-за проблемы с использованием рекурсии.В этом случае моя ошибка исходит из
Исключение в потоке "main" java.lang.StackOverflowError в quicksort.Quicksort.quickSort (Quicksort.java:36)
, что ..
if (first < last) {
int pivindex = partition(arr, first, last);
quickSort(arr, first, pivindex-1);
quickSort(arr, pivindex+1, last);
}