29

Я читал про разные типы сортировок, пять из которых известны всем хорошо. Я их легко освоил.

  1. Пузырьковая сортировка
  2. Сортировка вставкой
  3. Сортировка слиянием
  4. Сортировка выборкой
  5. Быстрая сортировка

Но есть две сортировки, которые я не смог понять (отличие от других, и когда они применимы). Это

  1. Карманная сортировка (блочная, Bucket Sort)
  2. Корневая сортировка (поразрядная, Radix Sort)

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

1
  • 1
    Я бы еще порекомендовал шейкерную, шелла и бинарными вставками посмотреть. 28 янв 2011 в 13:56

4 ответа 4

27

В отличие от сортировок 1–5, которые требуют от типа данных лишь операции сравнения, задающей линейный порядок, карманная и поразрядная (radix) сортировки предполагают, что нам известно больше о сортируемых элементах, за счёт чего они работают за O(n) от размера входных данных, преодолевая теоретический барьер O(n log(n)) для сортировок 1–5.

  1. Карманная сортировка (bucket sort)

    Этот алгоритм предполагает, что входные данные — числа, распределённые равномерно на некотором отрезке (скажем, [0; 1]). Разобьём этот отрезок на n частей, и распределим по ним данные n чисел. Ожидается, что в каждую часть попадёт немного элементов, а, значит, к ним можно применить простую и быструю сортировку (например, вставками). Ответом будет объединение результатов сортировки частей. Алгоритм требует O(n) дополнительной памяти и, в случае равномерного распределения входных данных, работает за O(n). Обоснование асимптотики.

  2. Поразрядная сортировка (radix sort)

    Этот алгоритм предполагает, что сортируются целые числа от 0 до C, представленные в позиционной системе счисления c основанием k (например, 2^8 или 2^16). Пойдём циклом по разрядам чисел от младших к старшим. Заведём массив count размером k, т.ч. count[i] = число элементов, имеющих в текущем разряде i (это делается линейным проходом по элементам). Далее, рассчитаем суммы на префиксах массива count (т.е. pref[i] это сумма count[j] для всех j меньше i. Теперь пройдёмся по сортируемым числам, кладя их в новом массиве на место pref[текущий разряд числа] и увеличивая этот элемент pref. После такого прохода за O(n + k) числа окажутся стабильно отсортированными по текущему разряду, а значит, в силу стабильности, и по всем более младшим разрядам. В конце все числа будут стабильно отсортированы. Работает данная реализация за O((n + k) * log_k(C)), что, в принципе, является O(n) (k и C от n не зависят). Также этот алгоритм можно модифицировать для быстрой сортировки строк в лексикографическом порядке, если развернуть внешний цикл и избежать копирования строк в процессе работы алгоритма. Некоторые реализации.

С практической точки зрения, когда сортируются числа, о которых не известно почти ничего, quicksort, обладая теоретически худшей асимптотикой, практически всегда обгоняет эти алгоритмы. В принципе, очень хорошо написанный radixsort может обогнать heapsort/mergesort, если от сортировки требуется стабильность. Bucketsort очень хорош, если входные данные подчиняются требуемому распределению, но это бывает не слишком часто.

7
  1. Блочная сортировка Идея в том чтобы пользуясь какими-то известными заранее свойствами входных данных раскидать последовательность в n корзин. После этого все, что попало в отдельную корзину, сортируется либо рекурсивно таким же методом, либо другими методами. Если известно что данные раскидываются по корзином равномерно, получится что в корзину попадет мало элементов и в среднем алгоритм будет работать за O(n)
  2. radix sort Применяется для сортировки последовательностей, сравниваемых лексикографически. Есть два варианта: либо сортировать с младшего положения к старшему стабильной сортировкой, либо отсортировать блочной сортировкой по первому символу, а затем корзины отсортировать рекурсивно по второму символу, и т.д.
4
  • Непонятна временная оценка для блочной сортировки. Если мы имеем на вход n элементов, мы можем раскидать их по к корзинам. Эту операцию мы выполним за O(n). Далее мы должны отсортировать каждую корзину. Если на этом шаге мы будем использовать, к примеру сортировку слиянием, то общее время будет O(n Log n). Если мы вызовем вызовем блочную сортировку рекурсивно, опять же, никак не выйдет O(n). В чем я ошибаюсь? 6 янв 2011 в 20:19
  • Мы пользуемся тем что данные распределены примерно равномерно, а значит в каждую корзину попадет O(1) элементов. Без дополнительных предположений об исходной последовательности преодолеть O(n*log(n)) все равно не получится
    – winger
    6 янв 2011 в 20:22
  • Получается, что мы за один проход ставим элемент на свое место в выходной последовательности? Не понятно как такое сделать. Такое возможно только при наличии частично упорядоченных данных. Данная сортировка не тянет на самостоятельность. Или мне не уловить идею. 6 янв 2011 в 20:27
  • 1
    Нет, фишка в том что в каждую корзину в среднем константное число элементов, которые мы потом быстро отсортируем внутри каждой корзины. Например если нам нужно сортировать равномерно распределенные на интервале [0,1) числа, можно раскидывать их по корзинам [0,1/n), [1/n,2/n),.., [(n-1)/n,1). Тогда по теории вероятности в каждый интервал попадает в среднем одно число (если их было n).
    – winger
    6 янв 2011 в 20:31
3

в книжке Каррано Ф.М., Причард Дж. Абстракция данных и решение задач на C++. Стены и зеркала приводится пример реализации последних двух сортировок и даются некоторые комментарии

3

на малочисленных объёмах данных рекоммендуется quicksort

на больших объёмах рекоммендуется merge sort, c использованием многопоточности

если по какой-то причине лучше не использовать многопоточность, например, данные не достаточно большие, чтобы ощутим был выигрыш от распаралеливания, или, просто одноядерная система на атомной станции, то лучше использовать heapsort, у которой асимптотика немного лучше

в стандартной библиотеке алгоритмов можно найти их реализации http://en.cppreference.com/w/cpp/algorithm

остальные алгоритмы сортировок, пожалуй, не имеет практического смысла в применении

2
  • Рекомендую познакомится с timsort и introsort.
    – Arnial
    22 дек 2016 в 9:26
  • 1
    @Arnial, спасибо, timsort использует merge sort (слиянием) и используется для ускорения сортировки уже частично сортированных данных - довольно специальный случай, но выглядит полезно. Что касается второго гибридного алгоритма, introsort - он использует quick sort и переключается на heap sort - heap sort не очень хорошо параллелится (см. specialmeaning.blogspot.com/2016/01/multi-thread-heap-sort.html) - практического толку для больших данных нет, а для маленьких да. Хотя можно и по размеру выбирать quicksort/heapsort. Выбирать quicksort/heapsort/mergesort - уже новый гибридный алгоритм. 23 дек 2016 в 4:41

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.