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

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

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

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

Кроме того, существует топологическая сортировка, оперерующая с ориентированными графами без циклов. Она приводит их представление в ЭВМ к виду, при котором все ребра направлены в одну сторону. С циклами такой фокус, естественно, не пройдет.

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

Тип \ параметры	Среднее время	Худшее время	Доп. требования к памяти под данные	Что выбрать? Примечания.
Пузырек	O ( n² )	O ( n² )	нет	Легок в реализации
Простые вставки	O ( n² )	O ( n² )	нет	Хорош для списков, частично упорядоченных и массивов n < 20
Сортировка Шелла	O ( n^1.25 )	O ( n^1.5 )	нет	Хорош для общего образования ;-), а также для n < 50
Быстрая сортировка	O(n log n)	O ( n² )	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)	ФАЙЛЫ	Универсальная внешняя сортировка.

Распределяющая и ее вариации.

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

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

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

Тип \ параметры	Среднее время	Худшее время	Доп. требования к памяти под данные	Что выбрать? Примечания.
Распределяющая сортировка	O ( k*n )	O ( k*n )	n	Чем m меньше n - тем лучше. Плоха для малых массивов и в случае m >> n
Быстрая сортировка с составными ключами.	O(n*logn)?	O(n²)?	log n	Гибрид быстрой и распределяющей. Хорош для случая m >> n. В этом случае она - наибыстрейшая.

Информацию о решении родственных сортировке задач можно также найти в разделе: Олимпиадные задачи: сортировки и последовательности.

Архив статей.

Д. Кнут. Сортировка и поиск: 3-й том 'Искусства программирования на ЭВМ'

Разные алгоритмы поиска и сортировки, описанные на серьезном теоретическом уровне.

Вверх по странице, к оглавлению и навигации