Сортировка ковша против быстрой сортировки

Question

Общий вопрос: Почему Bucket Сортировка выгоднее, чем Quick Sort?

Скажем, числа поступают из потока, а мои ведра - как (1,10) (11,20) ect ect.

Затем я сортирую ведра, а затем складываю их вместе со своими отсортированными числами.

ИЛИ

я могу поместить их в массив, а затем отсортировать их с Quicksort

Bucket Сортировка: Bestcase O (N + К) наихудший (N^2); Quicksort: Bestcase O (1) Averagecase O (nlogn) наихудший код (N^2);

Итак, почему мы используем сортировку ковша для таких вещей, как потоки входящих целых чисел, которые мы хотим отсортировать? Это потому, что мы можем принимать решения на основе количества целых чисел в каждом из ваших ковшей?

Благодаря

Answer 1

Если мы знаем, K фронт, и она мала (к < < п), то блочная сортировка может эффективно работать быстрее, чем Quicksort, так как п * журнала (п), в среднем по Quicksort, будет больше (n + k), что является средним для сортировки ковша.

т.е.

sortedList = (n*log(n) > n + k) ? bucketSort(list) : quicksort(list); 

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

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