Улучшенные сортировки

Сортировка простыми обменами

Пример сортировки

Предположим, что нужно отсортировать тот же набор чисел, при помощи которого мы иллюстрировали метод сортировки простыми вставками:

5 3 4 3 6 2 1

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

1 шаг: 53436212 шаг: 1343625 3 шаг: 1243635 {***}⁶⁾ 4 шаг: 1233645{ничего не делаем}5 шаг: 12336456 шаг: 1233465результат: 1233456

Рассмотренными сортировками, конечно же, не исчерпываются все возможные методы упорядочения массивов.

Существуют, например, алгоритмы, основанные на обмене двух соседних элементов: Пузырьковая и Шейкерная сортировки. Обе имеют сложность порядка N², однако и по скорости работы на любых входных данных, и по простоте реализации они проигрывают другим простым сортировкам. Поэтому мы настойчиво советуем читателю не прельщаться красивыми названиями, за которыми не стоит никакой особенной выгоды.

Тем же, кто все-таки желает ознакомиться с обменными сортировками, а также с подробными данными по сравнению различных сортировок, мы рекомендуем труды Д. Кнута⁷⁾ или Н. Вирта⁸⁾.

В отличие от простых сортировок, имеющих сложность ~N², к улучшенным сортировкам относятся алгоритмы с общей сложностью ~N*logN.

Необходимо, однако, отметить, что на небольших наборах сортируемых данных (N<100) эффективность быстрых сортировок не столь очевидна: выигрыш становится заметным только при больших N. Следовательно, если необходимо отсортировать маленький набор данных, то выгоднее взять одну из простых сортировок.

Дата добавления: 2014-01-03