Быстрое сортирование не начальный процесс сортировки

Question

Я (для домашней работы, если это влияет на ответы), предполагается, что он должен писать класс для быстрой сортировки для сортировки массива из файла txt или dat, предоставленного пользователем. Я представляю пользователю опцию меню в классе драйвера, чтобы выбрать тип сортировки, а затем передать массив классу quicksort для сортировки, после чего он возвращается обратно в класс драйвера, который должен быть записан в файл. Я верю, что возврат работает корректно, поскольку я получаю несортированный массив, напечатанный в файле, однако он, похоже, только один проход через цикл быстрой сортировки (определенный только одной печатью строки «Last Loop» на консоли.

Добавочные биты кода являются частью назначения, позволяя пользователю выбирать сортировку вставки, чтобы завершить сортировку, если в несортированном массиве осталось только 50 или 100 элементов на основе выбора пользователя. Я попытался запустить эту программу, комментируя эти два если утверждения выходят, и все еще программа не сортирует правильно. Я уверен, что ввод читается правильно, так как у меня есть добавочный класс HeapSort, который правильно сортирует, а сортировка вставки корректно возвращает, если этот параметр выбран, а размер файла меньше 50 или 100 ints. Похоже, я не могу получить QuickSort более крупного файла.

class Quicksort{ 
    int partition(int arr[], int lb, int ub){ 
    int i = lb, j = ub; 
    int temp; 
    int pivot = arr[0]; 
    while (i <= j) { 
     while (arr[i] < pivot){ 
      i++; 
     }while(arr[j] > pivot){ 
      j--; 
     }if (i <= j){ 
      temp = arr[i]; 
      arr[i] = arr[j]; 
      arr[j] = temp; 
      i++; 
      j--; 
     } 
    }return i; 
    } 

    int[] quicksort(int arr[], int lb, int ub, boolean insertLarge, boolean insertSmall){ 
    if (insertLarge && arr.length <= 100){ 
     System.out.println("Large"); 
     insertionSort(arr); 
    } 
    else if (insertSmall && arr.length <= 50){ 
     System.out.println("Small"); 
     insertionSort(arr); 
    } 
    else{ 
     int[] intArrCopy = new int[arr.length-1]; 
     for (int z = 1; z < intArrCopy.length; z++){ 
      intArrCopy[z-1] = arr[z]; 
     } 
     System.out.println("Last Loop"); 
     int index = partition(arr, lb, ub); 
     if (lb < index-1){ 
      quicksort(intArrCopy, lb, index-1, insertLarge, insertSmall); 
     }if (index < ub){ 
      quicksort(intArrCopy, index, ub, insertLarge, insertSmall); 
     } 
    }return arr; 
    } 

    public static void insertionSort(int x[]){ 
    int h, k, y; 
    for (k=1; k < x.length; k++){ 
     y = x[k]; 
     for (h = k-1; h>=0 && y < x[h]; h--){ 
      x[h+1] = x[h]; 
     }x[h+1] = y; 
    } 
    } 
} 

И как она вызывается из класса драйвера:

private static void processChoice(int choice, int[] intArr){ 
    switch (choice){ 
    case 1: 
     p = intArr.length; 
     output = new int[p]; 
     startTime = System.nanoTime(); 
     output = quick.quicksort(intArr, intArr[0], intArr[p-1], insertLarge, insertSmall); 
     endTime = System.nanoTime(); 
     System.out.println("Time Taken: "+(endTime-startTime)+" nanoseconds."); 
     break; 
    } 
} 

Answer 1

Если предположить, что гибридный сорт, попробовать что-то вроде этого:

void quicksort(int arr[], int lb, int ub){ 
    if ((ub-lb) < 100){    // < 32 may be fastest 
     System.out.println("Large"); 
     insertionSort(arr, lb, ub); 
     return; 
    } 
    int index = partition(arr, lb, ub); 
    if (lb < index-1) 
     quicksort(arr, lb, index-1); 
    if (index < ub) 
     quicksort(arr, index, ub); 
    } 

    public static void insertionSort(int x[], int lb, int ub){ 
    int h, k, y; 
    for (h = lb+1; h <= ub; h++){ 
     y = x[h]; 
     for (k = h; k > lb && x[k-1] > y; k--) 
      x[k] = x[k-1]; 
     x[k] = y; 
    } 
    }