Quicksort with inserting Сортировка - где я иду не так?

Question

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

Одним из требований является то, что он должен сортировать массив из 5 000 000 ints под 1300 мс (это на стандартных машинах, поэтому скорость процессора не является проблемой). Прежде всего, я не могу заставить его работать на 5 000 000 из-за ошибки переполнения стека (слишком много рекурсивных вызовов ...). Если я увеличу размер кучи, я все равно получаю намного медленнее, чем это.

Ниже приведен код. Любые намеки?

Заранее спасибо

public class MyQuickSort { 

    public static void sort(int [] toSort, int moveToInsertion) 
    { 
     sort(toSort, 0, toSort.length - 1, moveToInsertion); 
    } 

    private static void sort(int[] toSort, int first, int last, int moveToInsertion) 
    { 
     if (first < last) 
     { 
      if ((last - first) < moveToInsertion) 
      { 
       insertionSort(toSort, first, last); 
      } 
      else 
      { 
       int split = quickHelper(toSort, first, last); 
       sort(toSort, first, split - 1, moveToInsertion); 
       sort(toSort, split + 1, last, moveToInsertion); 
      } 
     } 
    } 

    private static int quickHelper(int[] toSort, int first, int last) 
    { 
     sortPivot(toSort, first, last); 
     swap(toSort, first, first + (last - first)/2); 
     int left = first; 
     int right = last; 
     int pivotVal = toSort[first]; 
     do 
     { 
      while ((left < last) && (toSort[left] <= pivotVal)) 
      { 
       left++; 
      } 

      while (toSort[right] > pivotVal) 
      { 
       right--; 
      } 

      if (left < right) 
      { 
       swap(toSort, left, right); 
      } 

     } while (left < right); 

     swap(toSort, first, right); 


     return right; 
    } 

    private static void sortPivot(int[] toSort, int first, int last) 
    { 
     int middle = first + (last - first)/2; 

     if (toSort[middle] < toSort[first]) swap(toSort, first, middle); 

     if (toSort[last] < toSort[middle]) swap(toSort, middle, last); 

     if (toSort[middle] < toSort[first]) swap(toSort, first, middle); 

    } 

    private static void insertionSort(int [] toSort, int first, int last) 
    { 
     for (int nextVal = first + 1; nextVal <= last; nextVal++) 
      { 
       int toInsert = toSort[nextVal]; 
       int j = nextVal - 1; 
       while (j >= 0 && toInsert < toSort[j]) 
       { 
        toSort[j + 1] = toSort[j]; 
        j--; 
       } 
       toSort[j + 1] = toInsert; 
      } 
    } 

    private static void swap(int[] toSort, int i, int j) 
    { 
     int temp = toSort[i]; 
     toSort[i] = toSort[j]; 
     toSort[j] = temp; 
    } 

} 

Answer 1

Выяснено.

На самом деле, не мои вины. Я генерировал числа между диапазоном 0-100 (для тестирования, чтобы убедиться, что он был отсортирован). Это привело к количеству дубликатов, что означало путь для многих разделов. Изменение диапазона до min_int и max_int заставляло его идти намного быстрее.

Спасибо за вашу помощь: D

Answer 2

Когда вводный массив велик, то его естественно ожидать, что рекурсивные функции столкнуться с проблемами переполнения стека. это то, что происходит здесь, когда вы пытаетесь использовать вышеуказанный код. Я бы рекомендовал вам написать итеративный QuickSort, используя ваш собственный стек. Он должен быть быстрым, потому что во время выполнения не выполняется распределение/освобождение фреймов стека. Вы также не столкнетесь с проблемами переполнения стека. Производительность также зависит от того, в какой момент вы запускаете сортировку вставки. У меня нет определенного размера ввода, где сортировка вставки плохо работает по сравнению с quicksort. Я предлагаю вам попробовать разные размеры, и я уверен, что вы заметите разницу.

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

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

Answer 3

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

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