Математика. Пути и Графы. Комбинаторика и перебор

Сортировка

Защита и сокрытие информации. Атаки и взлом

Сжатие информации и кодирование. СRC

Графика и обработка изображений. Фракталы

Поиск в строках, массивах,
последовательностях


Разбор выражений.
Компиляторы и интерпретаторы


Cтруктуры данных.
Хранение информации


AI, ГА, Нейронные сети

Вейвлеты

Игры, и все с ними связанное

Разное


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

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

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

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

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

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

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


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

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

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

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


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



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




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