Лекция № 7. Алгоритмы сортировки для абстрактных структур данных

Дополнительный материал по методам сортировки массивов к аудиторной лекции № 7, прочитанной 16 октября 2012 г. Обязателен для изучения.

1.Сортировка простыми включениями.

Предполагаем, что а₁,а₂,…,а_i-1 не упорядочены.. Назначается буферный элемент массива a₀.Элемент а₀ сравнивается со всеми имеющимися элементами до тех пор, пока не будет обнаружено между какими элементами он должен быть помещен: а_j и а_j-1. Все элементы, начиная с j-ого, сдвигаются вправо и вместо элемента j-1 -ого вставляется введенный элемент. Чтобы обеспечить контроль за длиной последовательности и не уйти за индекс, равный 1, вводится дополнительный, буферный элемент а₀. Этот элемент всегда будет равен вставляемому элементу, т.е. тому, который в данный момент сортируется. Количественные характеристики величин C и M можно найти в аудиторной лекции и литературе по алгоритмам.

Следовательно, окончание процесса сортировки обеспечивается двумя условиями:
1.Достигается барьер а₀ < а₀.

2.Достигается конец последовательности.

Среднее количество сравнений C_ср=0.25(n²+n-2). На рис. 1 показан алгоритм этого метода.

Пример:

36, 44, 8, 41, 56

8,36, 44, 41, 56

нет

8,36,41,44,56

_{Рис. 1}

2. Быстрая сортировка (по Хоору)

Алгоритм (рис. 2)

Рис. 2 Быстрая сортировка

Для ускорения процесса обмена предлагается обмениваться не упорядоченными элементами в последовательности на больших расстояниях. Выбирается средний элемент и весь массив просматривается с 1-ого элемента - слева направо, пока не будет найден элемент последовательности a_i, больший выбранного для сравнения X. Затем начинается просмотр последовательности с другого конца - движение справа налево, пока не будет найден элемент a_i<X. Теперь можно поменять местами эти элементы.

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