Выбор и быстрая сортировка не работают

Question

Я создаю программу, которая сравнивает многие виды и время, необходимое для завершения каждого из них. У меня проблемы с выбором и быстрой сортировкой. Ниже приведен код выбора:

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); 
     } 
    } 


} 

Самая последняя строка не будет работать в моей программе. Я не знаю, почему.

Вот основной код:

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 }, 


     }; 

Вот Быстрая сортировка. Эта строка не будет работать: QuickSort (список, pivotIndex + 1, последний);

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

Для вставки Сортировать - у вас есть переполнение стека. Литературный.

Вы не можете использовать рекурсивную реализацию с этими размерами в списке, поскольку это будет означать размер стека, линейный по отношению к входу.

См What is the maximum depth of the java call stack?

Вы должны реализовать итеративно, если вы хотите, чтобы проверить списки с такими огромными числами элементов.

---

Ваш главный код завинчен. Вы генерируете только два набора списков, которые затем отлично сортируются по первому алгоритму, а остальные алгоритмы затем получают отсортированный список в качестве входных данных.

Это, возможно, уже вызывая переполнение стека в вашем реализации Quicksort а также, как Quicksort, при выборе элемента поворота не случайно, бежит в Absolut худшем поведения случае, когда список либо сортируется совершенно в порядке возрастания или убывания заказ.

---

Если вы действительно хотите, чтобы подчеркнуть алгоритмы (и это будет вызвать переполнение стека с Quicksort), не испытывают только рандомизированные массивы, но и два краевых случая списка, который либо уже отсортированные в порядке убывания или возрастания.

Для большинства алгоритмов поиска любой из этих случаев вызывает наихудшее поведение, в то время как другой обычно вызывает лучший случай. (Или оба являются наихудшими, это может случиться и так!)