Я студент информатики и пытаюсь узнать о быстрой сортировке на Java. Я реализовал свою собственную версию, и я уверен, что это, вероятно, не самая лучшая реализация, так что не стесняйтесь со мной, это для целей обучения. Для того, чтобы узнать, я хотел бы знать, почему моя быстрая сортировка выдает мне следующую ошибку, которую я не могу решить или понять. Заранее спасибо!
Exception in thread "main" java.lang.StackOverflowError
at java.io.FileOutputStream.write(FileOutputStream.java:326)
at java.io.BufferedOutputStream.flushBuffer(BufferedOutputStream.java:82)
at java.io.BufferedOutputStream.flush(BufferedOutputStream.java:140)
at java.io.PrintStream.write(PrintStream.java:482)
at sun.nio.cs.StreamEncoder.writeBytes(StreamEncoder.java:221)
at sun.nio.cs.StreamEncoder.implFlushBuffer(StreamEncoder.java:291)
at sun.nio.cs.StreamEncoder.flushBuffer(StreamEncoder.java:104)
at java.io.OutputStreamWriter.flushBuffer(OutputStreamWriter.java:185)
at java.io.PrintStream.write(PrintStream.java:527)
at java.io.PrintStream.print(PrintStream.java:669)
at java.io.PrintStream.println(PrintStream.java:806)
at myQuickSort.mySwapMethod(myQuickSort.java:116)
at myQuickSort.partition(myQuickSort.java:52)
at myQuickSort.myQuickSortMethod(myQuickSort.java:39)
at myQuickSort.myQuickSortMethod(myQuickSort.java:40)
at myQuickSort.myQuickSortMethod(myQuickSort.java:40)
моя реализация Java Quicksort:
public class myQuickSort {
private int[] array;
public static void main(String[] args) {
int[] array = new int[] {3,5,74,3,67,45,23,6,34,12,889,4,25,1,0,7,4};
myQuickSort test = new myQuickSort(array);
System.out.println("Before:");
for(int i =0; i < array.length;i++) {
System.out.print(array[i]+",");
}
System.out.println("\n");
test.myQuickSortMethod(0, array.length -1);
System.out.println("After:");
for(int i =0; i < array.length;i++) {
System.out.print(array[i]+",");
}
}
public myQuickSort(int[] array) {
this.array = array;
}
public void myQuickSortMethod(int indexStart, int indexEnd) {
if(indexStart == indexEnd) {
return;
}
int whereToSplit = partition(indexStart,indexEnd);
myQuickSortMethod(indexStart, whereToSplit-1);
myQuickSortMethod(whereToSplit+1,indexEnd);
}
private int partition(int indexStart, int indexEnd) {
int leftOfPivotIndex = indexStart; //left pointer
int rightOfPivotIndex = indexEnd; //right pointer
int pivotIndex =indexStart+(indexEnd-indexStart)/2; //pivot chosen from the middle of the list
//swapping pivot with the first element of the array
mySwapMethod(indexStart,pivotIndex);
pivotIndex = indexStart;
if(indexStart != indexEnd) {
leftOfPivotIndex++;
}
while(leftOfPivotIndex <= rightOfPivotIndex) {
//left - pointer
while(array[leftOfPivotIndex] < array[pivotIndex] && leftOfPivotIndex < rightOfPivotIndex ) {
leftOfPivotIndex++;
}
//right-pointer loop
while(array[rightOfPivotIndex] >= array[pivotIndex] && leftOfPivotIndex < rightOfPivotIndex ) {
rightOfPivotIndex--;
}
mySwapMethod(leftOfPivotIndex,rightOfPivotIndex);
if(leftOfPivotIndex == rightOfPivotIndex) {
System.out.println("BREAKING CASE");
if(array[leftOfPivotIndex] <= array[pivotIndex]) {
mySwapMethod(pivotIndex,leftOfPivotIndex);
return leftOfPivotIndex;
}else {
mySwapMethod(pivotIndex,leftOfPivotIndex -1);
return leftOfPivotIndex -1;
}
}else {
//Move both left and write pointers after the swap
leftOfPivotIndex++;
rightOfPivotIndex--;
}
if(leftOfPivotIndex == rightOfPivotIndex || leftOfPivotIndex > rightOfPivotIndex) {
System.out.println("BREAKING CASE");
if(array[leftOfPivotIndex] < array[pivotIndex]) {
mySwapMethod(pivotIndex,leftOfPivotIndex);
return leftOfPivotIndex;
}else {
mySwapMethod(pivotIndex,leftOfPivotIndex -1);
return leftOfPivotIndex -1;
}
}
}
return -1;
}
private void mySwapMethod(int leftIndex,int rightIndex) {
int temp = array[leftIndex];
array[leftIndex] = array[rightIndex];
array[rightIndex] = temp;
}
}