Алгоритмы сортировки


     Данный класс алгоритмов делится на два основных подкласса:

     Внутренняя сортировка оперирует с массивами, целиком помещающимися в оперативной памяти с произвольным доступом к любой ячейке. Данные обычно сортируются на том же месте, далее ' на месте '.

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

Обычная сортировка


Тип \ параметры
Среднее время
Наихудшее время
Дополнительные требования к памяти под данные
Оптимальность
Пузырек
O ( n2 )
O ( n2 )
на месте
Легок в реализации
Простые вставки
O ( n2 )
O ( n2 )
на месте
Хорош для списков,
частично упорядоченных и массивов n < 20
Быстрая сортировка
O(n log n)
O ( n2 )
log n
Быстрейший метод для больших, разупорядоченных массивов n >50. Наихудший случай маловероятен.
Пирамидальная сортировка
O(n log n)
O(n log n)
на месте
В 1.5 раза медленнее быстрой сортировки, но на месте и всегда O(n log n).
Многофазная сортировка
не закончено: сканер
O(n log n)
O(n log n)
внешняя
памяти не требуется
Комбинированная сортировка
O(n log n)
O(n log n)
внешняя
берет, сколько дадут


Дискретная сортировка


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

     Прекрасный пример - строки: там каждая буква - одна из 33-х. Или целые числа от нуля до 65535.

     В современных ЭВМ все ключи, даже дробные числа представлены в памяти через конкретные целые числа, поэтому, в принципе, дискретную сортировку можно использовать везде, однако когда возможных значений ключей много больше, чем самих ключей, она очень невыгодна.
     Пусть далее имеем k байт в каждом ключе ( хотя, за единицу измерения вполне можно принять и что-либо другое. В том числе и 2 байта ; - ) ).
     Разрядность данных - m


Тип \ параметры
Среднее время
Наихудшее время
Дополнительные требования к памяти под данные
Оптимальность
Поразрядная сортировка
O ( k*n )
O ( k*n )
n
Чем m меньше n - тем лучше.
Плоха для малых массивов и в случае m >> n
Быстрая сортировка с составными ключами.
Опиcание в статье - 106k
O ( n*logn ) ?
O ( n ) ?
log n
Переработка поразрядной сортировки
для m >> n.
В этом случае она - наибыстрейшая.
*Coming soon




Вверх
вверх