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

UptoLike

ВУЗ: 

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

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

Рубрика: 

115
Максимальное число сравнений равно сумме членов арифметической
прогрессии 1 + 2 + 3 + . . . + (N–1) и определяется по форму
N-1
C
max
= Σ (N–i) = 0,5N(N–1).
i=1
Если исходная последовательность имеет обратную упорядоченность,
то для сортировки потребуется минимальное число сравнений C
min
= N–1.
Среднее число сравнений пропорционально 0,25N
2
.
Минимальное число перестановок равно нулю для случая, когда исход-
ная последовательность уже упорядочена. Максимальное число перестановок
потребуется для сортировки исходной последовательности, имеющей обратную
упорядоченность. Среднее число перестановок пропорционально 0,25N
2
.
Метод подсчета. Как и в предыдущем методе упорядоченная последо-
вательность В создается на свободном участке памяти в результате сортировки
исходной последовательности А. Метод основан на том, что (k+1)-й элемент
упорядоченной последовательности B превышает ровно k элементов и, следова-
тельно, занимает (k +1)-ю позицию. В каждом i-м проходе i-
й элемент исходной
последовательности А попарно сравнивается со всеми остальными элементами.
Если A(i) > A(j), то значение числа k оказывается равным числу элементов,
меньших, чем А(i). Номер позиции i-го элемента в последовательности В равен
k+1. Пример сортировки методом подсчета показан на рис. 8.4.
i 1 2 3 4 5 6 7 8 9 10
A(i) 15 8 19 21 12 7 3 1 9 17
№ прохода 1 2 3 4 5 6 7 8 9 10
k 6 3 8 9 5 2 1 0 4 7
В(k+1) 1 3 7 8 9 12 15 17 19 21
Рис. 8.4. Пример сортировки методом подсчета
В первом проходе устанавливается, что первый элемент исходной по-
следовательности А(1) = 15 оказался больше шести элементов и для него уста-
навливается k=6. Этот элемент займет 7-ю позицию в упорядоченной последо-
вательности В. Аналогично определяются позиции всех остальных элементов
последовательности B.
Для сортировки методом подсчета последовательности из
N элементов
требуется N проходов, на каждом проходе выполняется N сравнений. Числа
проходов и сравнений не зависят от степени упорядоченности исходной после-
довательности. Поэтому для данного метода максимальное, минимальное и
среднее число сравнений равно N
2
.
Метод подсчета применим только в том случае, когда в исходной по-
следовательности отсутствуют одинаковые элементы, иными словами, когда в
упорядочиваемом массиве нет записей с одинаковыми значениями ключей.

Страницы