Внедрение QuickSort в Java

Я студент-информатик, и я пытаюсь узнать о Quicksort на Java. Я внедрил свою собственную версию, и я уверен, что это, вероятно, не лучшая реализация, поэтому не будьте слишком тяжелы для меня, это для учебных целей. Чтобы узнать, что я хотел бы знать, почему мой QuickSort дает мне следующую ошибку, которую я, похоже, не могу решить или понять. Заранее спасибо!

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; 
 }
 }
1 ответ

Текущий выход:

Before:
3,5,74,3,67,45,23,6,34,12,889,4,25,1,0,7,4,

BREAKING CASE
BREAKING CASE
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1
 at com.algorithm.sorting.myQuickSort.mySwapMethod(myQuickSort.java:98)
 at com.algorithm.sorting.myQuickSort.partition(myQuickSort.java:48)

Причина в том, что вы не управляете индексом как

Я предлагаю вам использовать любую IDE и отлаживать собственный код https://www.jetbrains.com/help/idea/debugging-your-first-java-application.html

licensed under cc by-sa 3.0 with attribution.