Методы программирования. Громов Ю.Ю - 61 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

61
а) сортировка вставками. Элементы просматриваются по одному,
и каждый новый элемент вставляется в подходящее место среди ранее
упорядоченных элементов;
б) обменная сортировка. Если два элемента расположены не по по-
рядку, то они меняются местами. Этот процесс повторяется до тех пор,
пока все элементы не будут упорядочены;
в) сортировка посредством выбора. Сначала выбирается наимень-
ший (или наибольший) элемент и каким-либо образом отделяется от ос-
тальных, затем выбирается наименьший (наибольший) из оставшихся и
так далее до тех пор, пока не будут выбраны все элементы;
г) сортировка подсчётом. Каждый элемент сравнивается со всеми
остальными. Окончательное положение элемента определяется после
подсчёта числа меньших ключей.
На самом деле разработано множество различных алгоритмов сор-
тировки и каждый из них имеет свои преимущества и недостатки. Только
изучив характеристики каждого алгоритма сортировки, можно произво-
дить разумный выбор алгоритмов для конкретных приложений.
Рассмотрим сортировку подсчётом.
Ниже приведён алгоритм сортировки записей R
1
, R
2
, …, R
N
по клю-
чам K
1
, K
2
, …, K
N
, который использует для подсчёта числа ключей,
меньших данного, вспомогательную таблицу COUNT[1], COUNT[2], …,
COUNT[N]. После завершения алгоритма величина COUNT[j] + 1 опреде-
ляет окончательное положение записи R
j
.
Алгоритм C. (Сравнение и подсчёт.)
C1. [Сброс счётчиков.] Установить значения элементов COUNT[1],
COUNT[2], …, COUNT[N] равными нулю.
C2. [Цикл по i.] Выполнить шаг C3 для i = N, N – 1, …, 2 и завер-
шить работу алгоритма.
C3. [Цикл по j.] Выполнить шаг C4 для j = i – 1, i – 2, …, 1.
C4. [Сравнение ключей K
i
, K
j
.] Если K
i
< K
j
, то значение COUNT[j]
увеличить на один; в противном случае значение COUNT[i] увеличить на
один. ■
Заметим, что этот алгоритм даёт верный результат независимо от
числа равных ключей.
Пусть N = 16, а записи в памяти размещены так, что образуют сле-
дующую последовательность ключей:
K
503
87
512
61
908
170
897
275
653
426
154
509
612
677
765
703
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Тогда по окончании работы алгоритма C вспомогательная таблица
COUNT будет иметь следующий вид:

Страницы