Auswahl und Quick Sort funktioniert nicht

Question

Ich erstelle ein Programm, das viele Arten und die Zeit vergleicht, die es braucht, um jedes zu den anderen Sorten zu vervollständigen. Ich habe Probleme mit der Auswahl und schnellen Sortierung. Unten ist die Auswahl Sortiercode:

public class SelectionSort { 
    public static void SelectionSort(int[] list) { 
     Selection(list, 0, list.length - 1); // Sort the entire list 
    } 

    public static void Selection(int[] list, int low, int high) { 
     if (low < high) { 
      // Find the smallest number and its index in list(low .. high) 
      int indexOfMin = low; 
      int min = list[low]; 
      for (int i = low + 1; i <= high; i++) { 
       if (list[i] < min) { 
        min = list[i]; 
        indexOfMin = i; 
       } 
      } 

      // Swap the smallest in list(low .. high) with list(low) 
      list[indexOfMin] = list[low]; 
      list[low] = min; 

      // Sort the remaining list(low+1 .. high) 
      // Selection(list, (low + 1), high); 
     } 
    } 


} 

Die allerletzte Zeile wird nicht in meinem Programm funktionieren. Ich bin mir nicht sicher warum.

Hier ist der Hauptcode:

public Main() 
    { 

     Integer[] randH = new Integer[50000]; 
     int i=0; 
     while (i < randH.length) 
     {randH[i] = (int)(Math.random() * 50000); 
      i++;} 

     Integer[] randH2 = new Integer[100000]; 
     i=0; 
     while (i < randH2.length) 
     {randH2[i] = (int)(Math.random() * 100000); 
      i++;} 

     Integer[] randH3 = new Integer[150000]; 
     i=0; 
     while (i < randH3.length) 
     {randH3[i] = (int)(Math.random() * 150000); 
      i++;} 

     Integer[] randH4 = new Integer[200000]; 
     i=0; 
     while (i < randH4.length) 
     {randH4[i] = (int)(Math.random() * 200000); 
      i++;} 

     Integer[] randH5 = new Integer[250000]; 
     i=0; 
     while (i < randH5.length) 
     {randH5[i] = (int)(Math.random() * 250000); 
      i++;} 

     Integer[] randH6 = new Integer[300000]; 
     i=0; 
     while (i < randH6.length) 
     {randH6[i] = (int)(Math.random() * 300000); 
      i++;} 

     int[] rand = new int[50000]; 
     i=0; 
     while (i < rand.length) 
     {rand[i] = (int)(Math.random() * 50000); 
      i++;} 

     int[] rand1 = new int[100000]; 
     i=0; 
     while (i < rand1.length) 
     {rand1[i] = (int)(Math.random() * 100000); 
      i++;} 

     int[] rand2 = new int[150000]; 
     i=0; 
     while (i < rand2.length) 
     {rand2[i] = (int)(Math.random() * 150000); 
      i++;} 

     int[] rand3 = new int[200000]; 
     i=0; 
     while (i < rand3.length) 
     {rand3[i] = (int)(Math.random() * 200000); 
      i++;} 

     int[] rand4 = new int[250000]; 
     i=0; 
     while (i < rand4.length) 
     {rand4[i] = (int)(Math.random() * 250000); 
      i++;} 

     int[] rand5 = new int[300000]; 
     i=0; 
     while (i < rand5.length) 
     {rand5[i] = (int)(Math.random() * 300000); 
      i++;} 

     //Bubble Sort 

     long startTime = System.currentTimeMillis(); 
     new BubbleSort(rand); 
     long endTime = System.currentTimeMillis(); 
     long executionTime = endTime - startTime; 

     long startTime1B = System.currentTimeMillis(); 
     new BubbleSort(rand1); 
     long endTime1B = System.currentTimeMillis(); 
     long executionTime1B = endTime1B - startTime1B; 

     long startTime2B = System.currentTimeMillis(); 
     new BubbleSort(rand2); 
     long endTime2B = System.currentTimeMillis(); 
     long executionTime2B = endTime2B - startTime2B; 

     long startTime3B = System.currentTimeMillis(); 
     new BubbleSort(rand3); 
     long endTime3B = System.currentTimeMillis(); 
     long executionTime3B = endTime3B - startTime3B; 

     long startTime4B = System.currentTimeMillis(); 
     new BubbleSort(rand4); 
     long endTime4B = System.currentTimeMillis(); 
     long executionTime4B = endTime4B - startTime4B; 

     long startTime5B = System.currentTimeMillis(); 
     new BubbleSort(rand5); 
     long endTime5B = System.currentTimeMillis(); 
     long executionTime5B = endTime5B - startTime5B; 

     //Selection Sort 

     long startTime1S = System.currentTimeMillis(); 
     SelectionSort.SelectionSort(rand); 
     long endTime1S = System.currentTimeMillis(); 
     long executionTime1S = endTime1S - startTime1S; 

     long startTime2S = System.currentTimeMillis(); 
     SelectionSort.SelectionSort(rand1); 
     long endTime2S = System.currentTimeMillis(); 
     long executionTime2S = endTime2S - startTime2S; 

     long startTime3S = System.currentTimeMillis(); 
     SelectionSort.SelectionSort(rand2); 
     long endTime3S = System.currentTimeMillis(); 
     long executionTime3S = endTime3S - startTime3S; 

     long startTime4S = System.currentTimeMillis(); 
     SelectionSort.SelectionSort(rand3); 
     long endTime4S = System.currentTimeMillis(); 
     long executionTime4S = endTime4S - startTime4S; 

     long startTime5S = System.currentTimeMillis(); 
     SelectionSort.SelectionSort(rand4); 
     long endTime5S = System.currentTimeMillis(); 
     long executionTime5S = endTime5S - startTime5S; 

     long startTime6S = System.currentTimeMillis(); 
     SelectionSort.SelectionSort(rand5); 
     long endTime6S = System.currentTimeMillis(); 
     long executionTime6S = endTime6S - startTime6S; 

     //Heap Sort 

     long startTime1H = System.currentTimeMillis(); 
     HeapSort.HeapSort(randH); 
     long endTime1H = System.currentTimeMillis(); 
     long executionTime1H = endTime1H - startTime1H; 

     long startTime2H = System.currentTimeMillis(); 
     HeapSort.HeapSort(randH2); 
     long endTime2H = System.currentTimeMillis(); 
     long executionTime2H = endTime2H - startTime2H; 

     long startTime3H = System.currentTimeMillis(); 
     HeapSort.HeapSort(randH3); 
     long endTime3H = System.currentTimeMillis(); 
     long executionTime3H = endTime3H - startTime3H; 

     long startTime4H = System.currentTimeMillis(); 
     HeapSort.HeapSort(randH4); 
     long endTime4H = System.currentTimeMillis(); 
     long executionTime4H = endTime4H - startTime4H; 

     long startTime5H = System.currentTimeMillis(); 
     HeapSort.HeapSort(randH5); 
     long endTime5H = System.currentTimeMillis(); 
     long executionTime5H = endTime5H - startTime5H; 

     long startTime6H = System.currentTimeMillis(); 
     HeapSort.HeapSort(randH6); 
     long endTime6H = System.currentTimeMillis(); 
     long executionTime6H = endTime6H - startTime6H; 

     //Radix Sort 

     long startTime1R = System.currentTimeMillis(); 
     RadixSort.RadixSort(rand); 
     long endTime1R = System.currentTimeMillis(); 
     long executionTime1R = endTime1R - startTime1R; 

     long startTime2R = System.currentTimeMillis(); 
     RadixSort.RadixSort(rand1); 
     long endTime2R = System.currentTimeMillis(); 
     long executionTime2R = endTime2R - startTime2R; 

     long startTime3R = System.currentTimeMillis(); 
     RadixSort.RadixSort(rand2); 
     long endTime3R = System.currentTimeMillis(); 
     long executionTime3R = endTime3R - startTime3R; 

     long startTime4R = System.currentTimeMillis(); 
     RadixSort.RadixSort(rand3); 
     long endTime4R = System.currentTimeMillis(); 
     long executionTime4R = endTime4R - startTime4R; 

     long startTime5R = System.currentTimeMillis(); 
     RadixSort.RadixSort(rand4); 
     long endTime5R = System.currentTimeMillis(); 
     long executionTime5R = endTime5R - startTime5R; 

     long startTime6R = System.currentTimeMillis(); 
     RadixSort.RadixSort(rand5); 
     long endTime6R = System.currentTimeMillis(); 
     long executionTime6R = endTime6R - startTime6R; 

     //Quick Sort 

     long startTime1Q = System.currentTimeMillis(); 
     QuickSort.QuickSort(rand); 
     long endTime1Q = System.currentTimeMillis(); 
     long executionTime1Q = endTime1Q - startTime1Q; 

     long startTime2Q = System.currentTimeMillis(); 
     QuickSort.QuickSort(rand1); 
     long endTime2Q = System.currentTimeMillis(); 
     long executionTime2Q = endTime2Q - startTime2Q; 

     long startTime3Q = System.currentTimeMillis(); 
     QuickSort.QuickSort(rand2); 
     long endTime3Q = System.currentTimeMillis(); 
     long executionTime3Q = endTime3Q - startTime3Q; 

     long startTime4Q = System.currentTimeMillis(); 
     QuickSort.QuickSort(rand3); 
     long endTime4Q = System.currentTimeMillis(); 
     long executionTime4Q = endTime4Q - startTime4Q; 

     long startTime5Q = System.currentTimeMillis(); 
     QuickSort.QuickSort(rand4); 
     long endTime5Q = System.currentTimeMillis(); 
     long executionTime5Q = endTime5Q - startTime5Q; 

     long startTime6Q = System.currentTimeMillis(); 
     QuickSort.QuickSort(rand5); 
     long endTime6Q = System.currentTimeMillis(); 
     long executionTime6Q = endTime6Q - startTime6Q; 

     //Merge Sort 

     long startTime1M = System.currentTimeMillis(); 
     MergeSort.MergeSort(rand); 
     long endTime1M = System.currentTimeMillis(); 
     long executionTime1M = endTime1M - startTime1M; 

     long startTime2M = System.currentTimeMillis(); 
     MergeSort.MergeSort(rand1); 
     long endTime2M = System.currentTimeMillis(); 
     long executionTime2M = endTime2M - startTime2M; 

     long startTime3M = System.currentTimeMillis(); 
     MergeSort.MergeSort(rand2); 
     long endTime3M = System.currentTimeMillis(); 
     long executionTime3M = endTime3M - startTime3M; 

     long startTime4M = System.currentTimeMillis(); 
     MergeSort.MergeSort(rand3); 
     long endTime4M = System.currentTimeMillis(); 
     long executionTime4M = endTime4M - startTime4M; 

     long startTime5M = System.currentTimeMillis(); 
     MergeSort.MergeSort(rand4); 
     long endTime5M = System.currentTimeMillis(); 
     long executionTime5M = endTime5M - startTime5M; 

     long startTime6M = System.currentTimeMillis(); 
     MergeSort.MergeSort(rand5); 
     long endTime6M = System.currentTimeMillis(); 
     long executionTime6M = endTime6M - startTime6M; 







     //headers for the table 
     String[] columns = new String[] { 
       "Array Size", "Selection Sort", "Bubble Sort", "Merge Sort", "Quick Sort", "Heap Sort", "Radix Sort" 
     }; 

     //actual data for the table in a 2d array 
     Object[][] data = new Object[][] { 
       {50000, executionTime1S, executionTime, executionTime1M, executionTime1Q, executionTime1H, executionTime1R}, 
       {100000, executionTime2S, executionTime1B, executionTime2M, executionTime2Q, executionTime2H, executionTime2R }, 
       {150000, executionTime3S, executionTime2B, executionTime3M, executionTime3Q, executionTime3H, executionTime3R }, 
       {200000, executionTime4S, executionTime3B, executionTime4M, executionTime4Q, executionTime4H, executionTime4R }, 
       {250000, executionTime5S, executionTime4B, executionTime5M, executionTime5Q, executionTime5H, executionTime5R }, 
       {300000, executionTime6S, executionTime5B, executionTime6M, executionTime6Q, executionTime6H, executionTime6R }, 


     }; 

Hier ist die Schnell sortieren. Diese Zeile wird nicht funktionieren: QuickSort (list, pivotIndex + 1, last);

public class QuickSort { 
    public static void QuickSort(int[] list) { 
     QuickSort(list, 0, list.length - 1); 
    } 

    private static void QuickSort(int[] list, int first, int last) { 
     if (last > first) { 
      int pivotIndex = partition(list, first, last); 
      QuickSort(list, first, pivotIndex - 1); 
//   QuickSort(list, pivotIndex + 1, last); 
     } 
    } 

    /** Partition the array list[first..last] */ 
    private static int partition(int[] list, int first, int last) { 
     int pivot = list[first]; // Choose the first element as the pivot 
     int low = first + 1; // Index for forward search 
     int high = last; // Index for backward search 

     while (high > low) { 
      // Search forward from left 
      while (low <= high && list[low] <= pivot) 
       low++; 

      // Search backward from right 
      while (low <= high && list[high] > pivot) 
       high--; 

      // Swap two elements in the list 
      if (high > low) { 
       int temp = list[high]; 
       list[high] = list[low]; 
       list[low] = temp; 
      } 
     } 

     while (high > first && list[high] >= pivot) 
      high--; 

     // Swap pivot with list[high] 
     if (pivot > list[high]) { 
      list[first] = list[high]; 
      list[high] = pivot; 
      return high; 
     } 
     else { 
      return first; 
     } 
    } 


} 

Answer 1

Für die Insertion Sort - Sie haben einen Stapelüberlauf bekommen. Eine wörtliche.

Sie können die rekursive Implementierung nicht mit diesen Listengrößen verwenden, da dies eine Stapelgröße bedeuten würde, die linear zur Eingabe ist.

Siehe What is the maximum depth of the java call stack?

Sie müssen es iterativ implementieren, wenn Sie eine Liste mit so großen Anzahl von Elementen testen möchten.

---

Ihr Hauptcode ist geschraubt. Sie erzeugen nur zwei Sätze von Listen, die dann durch den ersten Algorithmus jeweils perfekt sortiert sind, und die anderen Algorithmen erhalten dann eine sortierte Liste als Eingabe.

Dies auslöst möglicherweise bereits einen Stapelüberlauf in Ihrem Quicksort Implementierung als auch, wie Quicksort, wenn das Schwenkelement die Auswahl nicht zufällig, die absolut schlimmsten Fall Verhalten läuft in, wenn die Liste entweder perfekt aufsteigend sortiert oder absteigend Auftrag.

---

Wenn Sie wirklich die Algorithmen betonen wollen (und das wird bewirken, dass der Stack-Überlauf mit Quicksort), nicht testen nur randomisierte Arrays, sondern auch die beiden Grenzfälle einer Liste, die sortiert entweder bereits in absteigender oder aufsteigender Reihenfolge.

Bei den meisten Suchalgorithmen löst jeder dieser Fälle das Worst-Case-Verhalten aus, während der andere den besten Fall auslöst. (Oder beides ist der schlimmste Fall, das kann auch passieren!)