Учебное пособие Самара 2015 + 004. 43 Ббк 32. 973 Н 19

N( N — 1)/2



(3^{2 N)/2 (13.2)}
операций сравнения, так как внешний цикл выполняется N — 1 раз, а внутренний N/2. Это выражение соответствует площади прямоугольного треугольника с катетами N и N — 1.
Число перестановок зависит от степени предварительной упорядоченности массива: В лучшем случае перестановки не вы- полняются (массив уже отсортирован в нужном направлении и число перестановок равно 0);
170
В среднем случае выполняется
N(N — 1)/4 = (3² 7\/)/4 (13.3)
перестановок (т.е. число сравнений делится пополам), число опе- раций присваивания оказывается утроенным, т.е.
3N(N — 1)/4. (13.4)
В худшем случае (массив отсортирован в обратном направ- лении) выполняется

перестановок или

^{N(N — 1)/2 =} (3^{2 7\/)/2}
(13.5)

(13.6)

операций присваивания.
Из-за наличия в формулах компонента N ^2! ырьковая сор-
тировка относится к N-квадратичным алгоритмам (см. рисунок 13.2). При работе с большими структурами данных (массивами или связными списками) пузырьковая сортировка неэффективна.




0

Рис. 13.2 — Зависимость времени работы от размера массива для N-квадратичных алгоритмов

Считается, что пузырьковая сортировка вообще является "учебной", но в реальности она может применяться для упорядо- чения массивов очень малого размера (3 — 7 элементов) в различ- ных алгоритмах обработки сигналов.

171

Hpouepypa nyssIJ3hKOBOii copT pOBKH Hit II3hIKé HIlCKllJIh.

var str: array[0..M] of char;

procedure bubble(item: array of char; n: in—
teger);
var
a, b: integer;
t: char;
begin
for a := 1 to n — 1 do
for b := n — 1 downto a do
if item[b-1] > item[b] then begin
t := item[b— 1]; { HepeCTaHO BKa }
item[b— 1] := item[b];
item[b] t end
end;

B0 BTO]3OM BiI]3H£tHTe npouepypsI n]3epn]3HHHMIIéTCII HOHhITKiI

3iIKOHUHTI› H]3OII CC CO]3TH]3OBKH QO 3 IB ]3III HHP BH IIIH FO IJHKJI I,
éCJIH BCé oJIéMéHTsI yme sIIHIIJIH CBOH nosHlJHH (T.é. éCJIH B OUé]3é@- HOM npoxope BHyTpeHHéFO IJHKJIiI He 6hIJIO BhIHOJIHéHO HH OQHO
OHé]3iIIlHH Hé]3éCTiIHOBKH) — 3TO COOTBéTcTByeT yCaoaum Aéaepcona (HJIH CHOdK P Aéaepcona). DTOT BII]3HIIHT H]3ouepypsi pJlHHHéé, HO Ho- 3BOJIIIéT H]3 «ypauHoM» pacnonoWéHHH COpTHpyeMsIX @IIHHhIX @é-
JI ITI› M HI›III H]3OXOQOB.

procedure bubbled(item: array of char; n: in- teger):

var
a, ssign, pass: integer; t: char;
begin
ssign 1;
pass 0:
while ssign <> 0 do begin
ssign 0;
pass := pass + 1;

172
for a:=0 to n — pass — 1 do

if item[a] > item[a = 1] then begin
t := item[a — 1];
item[a — 1] := item[a]; item[a] t;
ssign 1
end
end end;

AHIIJIOFHUHI›Ie yHKuHH HH II3I›IKIIX FH/CH+ .

void bubble(char* item, int n) int a, b;
char buf;
for (a = 1; a < n; +’a)
for (b = n - 1; b >= a; --b)
if (item[b - 1] > item[b])

buf = item[b - 1]; // MepeCTaH OBKa

item [b - 1] = item[b]; item[b] = buf;

BII]3HIIHT c ycnoBHéM A$ Bé]3COHfl (Hé]3éCTlIHOBKlI He HOKII3IIHII :

void bubble1(char* item, int n)

int a, ssign = 1, pass 0; char buf;

while(ssign)

ssign 0; pass’+;

for (a = 0; a < n — pass; a++) if (item[a] > item[a + 1])

173
// Перестановка ssign++;

Условие Айверсона является одной из попыток оптимиза- ции этого алгоритма для повышения его эффективности, но обычно все такие попытки, включая ручную оптимизацию ма- шинных команд, не приводят к заметному повышению скорости работы алгоритма.

Существуют текстовые модификации приведённых проце- дуры, в которых, например, счётчики обоих циклов меняются на увеличение и т.п.
Тип упорядоченности — по возрастанию или по убыванию зависит от знака операции сравнения текущего и последующего элементов.

3.