Главная Промышленная автоматика.

Сортировка вставками

Второй метод, который мы рассмотрим, называется сортировкой вставками, так как на i-M этапе мы "вставляем" i-й элемент A[i] в нркную позицию среди элементов А[1], А[2], A[i - 1], которые уже упорядочены. После этой вставки первые i элементов будут упорядочены. Сказанное можно записать в виде следующей псев-доирограммы:

for i:= 2 to л do

переместить AfiJ на позицию j й i такую, что AfiJ < А[к] для j < А: < / и либо A[i] S Afj - 1], либо j = 1

Чтобы сделать процесс перемещения элемента A[i] более простым, полезно ввести элемент А[0], чье значение ключа будет меньше значения ключа любого элемента А[1], А[п]. Мы можем постулировать существование константы - оо типа keytype, которая будет меньше значения ключа любой записи, встречающейся на практике. Если такую константу нельзя применить, то при вставке AfiJ в позицию / - 1 надо проверить, не будет ли j = 1, если нет, тогда сравнивать элемент A[i] (который сейчас находится в позиции j) с элементом A[f - 1]. Описанный алгоритм показан в листинге 8.3.

Листинг 8.3. Сортировка вставками

(1) а[0] .кву:= - со;

(2) for i; = 2 to n do begin

(3) j:= i;

(4) while A[j] < A[j - 1]

(5) swap(A[j], A[j -

(6) j:= 7 - 1 end

Пример 8.2. В табл. 8.3 показан начальный список из табл. 8.1 и последовательные этапы алгоритма вставкой для i = 2, 3, 6. После каждого этапа алгоритма элементы, расположенные выше линии, уже упорядочены, хотя между ними на последующих этапах могут быть вставлены элементы, которые сейчас находятся ниже линии. D

Таблица 8.3. Этапы сортировки вставками

do begin

1]);

Пили

Этна Кракатау Агунг Св. Елена

Везувий

- 00

Пили Этна

Кракатау Агунг Св. Елена Везувий

- 00

Кракатау

Пили

Этна

Агунг

Св. Елена

Везувий

Агунг Кракатау Пили Этна

Св. Елена Везувий

Агунг Кракатау Пили Св. Елена

Этна Везувий

Агунг

Везувий

Кракатау

Пили

Св. Елена

Этна

Начальное положение i - 2

I = 3

i = 5

I = 6



Сортировка посредством выбора

Идея сортировки посредством выбора таюке элементарна, как и те два метода сортировки, которые мы уже рассмотрели. На i-м этапе сортировки выбирается запись с наименьшим ключом среди записей ...,А[п] и меняется местами с записью A[t]. В результате после i-ro этапа все записи А[1], Ali] будут упорядочены. Сортировку посредством выбора можно описать следуюшим образом:

for i:=lton~ldo

выбрать среди АЦ], А[л] элемент с наименьшим ключом и

поменять его местами с A[i];

Более полный код, реализующий этот метод сортировки, приведен в листинге 8.4. Листинг 8.4. Сортировка посредством выбора

lowkеу: keytype;

текущий натоеньшии ключ, найденный

при проходе по элементам А[i J , . . lowindex: integer; { позиция элемента

A[n] }

ключом lowkey }

begin

(2) (3) (4)

(5) (6) (7)

i:= 1 to л - 1 do begin lowindex:= i; lowkey: = A[i] .key;

tor j:= i + 1 to л do

{ сравнение ключей с текущто ключом Iowkey } if A[j] .key < lowkey then begin i owkey:= A[j].key; lowindex:= j

end;

swap(A[i] r A[ lowindex])

end;

Пример 8.3. В табл. 8.4 показаны этапы сортировки посредством выбора для списка из табл. 8.1. Например, на 1-м этапе значение lowindex равно 4, т.е. позиции Агунга, который меняется с Пили, элементом А[1].

Линии в табл. 8.4 показывают, что элементы, расположенные выше ее, имеют наименьшие значения ключей и уже упорядочены. После (п - 1)-го этапа элемент А[п] таюке стоит на "правильном" месте, так как выше его все записи имеют меньшие значения ключей. D

Таблица 8.4. Сортировка посредством выбора

Агунг

Пили Этна Кракатау Агунг Св. Елена Везувий

Этна Кракатау Пили Св. Елена Везувий

Агунг Везувий

Кракатау Пили Св. Елена Этна

Агунг Везувий Кракатау Пили Св. Елена Этна

Агунг

Везувий

Кракатау

Пили

Св. Елена

Этна

Агунг

Везувий

Кракатау

Пили

Св. Елена

Этна

Начальное положение 1-й этап

2-й этап

3-й этап

4-й этап

5-й этап



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

Методы "пузырька", вставками и посредством выбора имеют временн{/ю слокность на последовательностях из и элементов. Рассмотрим метод "пузырька" (листинг 8.1). Независимо от того, что подразумевается под типом recordtype, выполнение процедуры swap требует фиксированного времени. Поэтому строки (3), (4) затрачивают Ci единиц времени; - некоторая константа. Следовательно, для фиксированного значения i цикл строк (2) - (4) требует не больше cz(re - i) шагов; - константа. Последняя константа несколько больше константы Ci, если учитывать операции с индексом j в строке (2). Поэтому вся программа требует

+с2(п- о = гг" + (сз - С)П

шагов, где слагаемое Сзп учитывает операции с индексом i в строке (1). Последнее выражение не превосходит <с2/2 + Сз)п для п > 1, поэтому алгоритм "пузырька" имеет временную сложность О(п). Нижняя временная граница для алгоритма равна СЦп% поскольку если даже не выполнять процедуру swap (например, если список уже отсортирован), то все равно п{п - 1)/2 раз выполняется проверка в строке (3).

Далее рассмотрим сортировку вставками (листинг 8.3). Цикл while в строках (4) - (6) выполняется не более 0(i) раз, поскольку начальное значение у равно i, а затем j уменьшается на 1 при кавдом выполнении этого цикла. Следовательно, цикл for

строк (2) - (6) потребует не более с" i шагов для некоторой константы с. Эта сумма имеет порядок О(ге).

Читатель может проверить, что если список записей первоначально был отсортирован в обратном порядке, то цикл while в строках (4) - (6) выполняется ровно i - 1

раз, поэтому строка (4) выполняется X"=г~~ ("-1)/2 раз. Следовательно, сортировка вставками в самом худшем случае требует времени не менее Q(n). Можно показать, что нижняя граница в среднем будет такой же.

Наконец, рассмотрим сортировку посредством выбора, показанную в листинге 8.4. Легко проверить, что внутренний цикл в строках (4) - (7) требует времени порядка 0(ге - i), поскольку; здесь изменяется от i -Ь 1 до и. Поэтому обшее время выполнения алгоритма составляет (п - О для некоторой константы с. Эта сумма, равная сп(ге - 1)/2, имеет порядок роста О(ге). С другой стороны, нетрудно показать, что строка (4) выполняется не менее J" XLi ~ разнезависимо от начального списка сортируемых элементов. Поэтому сортировка посредством выбора требует времени не менее Й(ге) в худшем случае и в среднем.

Подсчет перестановок

Если размер записей большой, тогда процедура swap для перестановки записей, которая присутствует во всех трех вышеописанных алгоритмах, занимает больше времени, чем все другие операции, выполняемые в программе (например, такие как сравнение ключей или вычисление индексов массива). Поэтому, хотя мы уже показали, что время работы всех трех алгоритмов пропорционально п, необходимо более детально сравнить их с учетом использования процедуры swap.

Сначала рассмотрим алгоритм "пузырька". В этом алгоритме процедура swap выполняется (см. листинг 8.1, строка (4)) не менее 1 , ,(1г п(п-\)/2рга, т.е.

почти раз. Но поскольку строка (4) выполняется после условного оператора в строке (3), то можно ожидать, что число перестановок значительно меньше, чем

В самом деле, в среднем перестановки выполняются только в половине из всех возможных случаев. Следовательно, ожидаемое число перестановок, если все воз-





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 [73] 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123

0.0026