Лекции - Структуры и алгоритмы компьютерной обработки данных / 4.Задача сортировки. Устойчивость. Алгоритмы внутренней сортировки. Простейшие алгоритмы

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

• Алгоритмы внутренней сортировки (требуют произвольного доступа к элементам) обычно используются для сортировки в оперативной памяти

• Алгоритмы внешней сортировки (обращаются к данным последовательно) применяются для сортировки файлов

Алгоритмы внешней сортировки обычно работают медленнее и требуют большого объема дополнительной памяти.

Устойчивость сортировки

Устойчивый алгоритм сохраняет относительный порядок следования записей с одинаковыми ключами.

Пример: сортировка алфавитного списка студентов по экзаменационной оценке.

Не все быстрые алгоритмы являются устойчивыми.

Объемная сложность сортировки

Многие алгоритмы требуют дополнительной памяти для сохранения копии сортируемого массива

Временная сложность сортировки, основанной на сравнениях

Алгоритм сортировки можно представить в виде разрешающего дерева.

Число сравнений в худшем случае – высота разрешающего дерева h. В дереве n! листьев => n! ≤ 2h => log (n!) ≤ h => h = Ω (n log n)

У простых алгоритмов сортировки сложность Ө(n2), у более сложных - Ө(n log n)

Сортировка прямыми вставками

На i-ом шаге элемент a[i] вставляется на нужное место в уже отсортированную последовательность a[1]…a[i-1]. Для этого элемент сравнивается с предыдущим и либо ставится на место, либо предыдущий элемент сдвигается вправо, и операция повторяется со следующим элементом.

Сложность в лучшем случае Ө(n), в худшем и среднем Ө(n2).

Сортировку вставками следует применять в случае, когда последовательность почти упорядочена.

Сортировка прямым выбором

Сначала выбираем элемент с наименьшим ключом. Затем меняем его местами с первым элементом. Среди оставшихся ищем элемент с наименьшим ключом и меняем его и второй элемент местами. Процесс продолжается, пока не останется один, самый большой элемент.

Число сравнений не зависит от порядка элементов и равно

(n-1)+(n-2)+…+1 = (n2-n)/2 = Ө(n2).

Число обменов будет Ө(n).

Сортировку выбором можно использовать, если сложность обмена значительно больше, чем сложность сравнения.

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

По-другому называется пузырьковой сортировкой.

Сравниваем между собой два соседних элемента. Если элемент с большим ключом левее, то меняем их местами. В результате прохода по всему массиву наибольший элемент окажется на последнем месте (“всплывет”). На следующем проходе на место встанет второй по величине ключа элемент. Всего для сортировки требуется n-1 проход.

Количество сравнений и обменов в худшем случае равно (n2-n)/2 = Ө(n2).

Все простые алгоритмы сортировки устойчивы.