Введение в информационные системы. Брюхомицкий Ю.А. - 111 стр.

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

Составители: 

Рубрика: 

111
В зависимости от используемого метода сортировки, упорядоченная
последовательность размещается на том же участке памяти, что и исходная, или
требует для своего формирования свободного участка памяти.
Основными методами сортировки являются: метод выбора, метод об-
мена, метод вставок, метод подсчета, метод Шелла. Существуют также много-
численные модификации и сочетания этих методов. При
иллюстрации методов
сортировки для упрощения предполагается, что записи состоят только из поля
ключа, т.е. элементами упорядочиваемых последовательностей являются значе-
ния ключей записей.
Метод выбора. При сортировке этим методом упорядоченная последо-
вательность создается на том же участке памяти, что и исходная. В течение пер-
вого прохода осуществляется поиск наименьшего элемента. После
того как эле-
мент найден, его меняют местами с первым элементом исходной последова-
тельности, в результате чего наименьший элемент занимает первую позицию в
формируемой последовательности. Затем осуществляется поиск следующего
наименьшего элемента среди оставшихся. Найденный элемент меняется места-
ми со вторым элементом исходной последовательности. После 2-го прохода
получим сформированную последовательность из 2-
х элементов, первый из ко-
торых меньше второго. Процесс поиска и последовательного размещения эле-
ментов повторяется до тех пор, пока все элементы не будут отсортированы в
восходящем порядке.
Пример сортировки исходной неупорядоченной последовательности
A(i) = {15, 11, 12, 9, 7, 2, 5, 3, 8, 1} методом выбора показан на рис. 8.1. Цифры в
рамках на рис. 8.1 означают записи с наименьшим ключом, выбранные
на дан-
ном проходе, затемненные участки последовательности являются уже отсорти-
рованными.
Для сортировки методом выбора последовательности A(i), состоящей из
N элементов, в общем случае требуется N–1 проход. Для i-го прохода требуется
N–i сравнений. Следовательно, общее число сравнений определится как
Число сравнений не зависит от степени упорядоченности
исходной по-
следовательности, поэтому приведенное соотношение определяет минимальное,
максимальное и среднее число сравнений. Для оценки среднего числа сравне-
ний можно использовать также аппроксимацию C
ср
= 0,5N
2
. Для примера, при-
веденного на рис. 8.1, использование аппроксимированного соотношения дает
С
ср
= 0,5·10
2
= 50. Фактическое значение С = 0,5N(N-1) = 0,5·10(10–1) = 45.
N-1
C = (N–i) = 0,5N(N–1).
i=1

Страницы