Сортировка простыми обменами
Пример сортировки
Предположим, что нужно отсортировать тот же набор чисел, при помощи которого мы иллюстрировали метод сортировки простыми вставками:
5 3 4 3 6 2 1Теперь мы будем придерживаться алгоритма ПрВыб (подчеркнута несортированная часть массива, а квадратиком выделен ее минимальный элемент):
1 шаг: 53436212 шаг: 1343625 3 шаг: 1243635 {***}6Если бы в строке {***} программы ПРВыб стоял знак строгого неравенства, то в качестве минимума была бы выбрана первая тройка. Однако очевидно, что выгоднее брать последний из совпадающих элементов: благодаря этому все они оказываются левее, чем тот превосходящий всех их элемент, с которым выбранный минимум меняется местами. 4 шаг: 1233645{ничего не делаем}5 шаг: 12336456 шаг: 1233465результат: 1233456Рассмотренными сортировками, конечно же, не исчерпываются все возможные методы упорядочения массивов.
Существуют, например, алгоритмы, основанные на обмене двух соседних элементов: Пузырьковая и Шейкерная сортировки. Обе имеют сложность порядка N2, однако и по скорости работы на любых входных данных, и по простоте реализации они проигрывают другим простым сортировкам. Поэтому мы настойчиво советуем читателю не прельщаться красивыми названиями, за которыми не стоит никакой особенной выгоды.
Тем же, кто все-таки желает ознакомиться с обменными сортировками, а также с подробными данными по сравнению различных сортировок, мы рекомендуем труды Д. Кнута7Д. Кнут. Искусство программирования для ЭВМ. Т.3. Сортировка и поиск (любое издание). или Н. Вирта8Н. Вирт. Алгоритмы и структуры данных (любое издание)..