Материал: Мансуров. Основы программирования в среде Lazarus. 2010

4.1 Алгоритмы сортировки

____________________________________________________________________

начало

Ввод массива x

j=j-1

да

j i

нет

i=i+1

да

i n

нет

Вывод отсортированного массива x

конец

Рис. 4.4 Блок-схема алгоритма сортировки методом "пузырька".

begin

count:= high(vector); for i:= 1 to count do for j:= count downto i do

if vector[j - 1] > vector[j] then begin

temp:= vector[j - 1]; vector[j - 1]:= vector[j]; vector[j]:= temp;

276

Глава 4 Типовые алгоритмы обработки информации

____________________________________________________________________

end

end;

begin

writeln(UTF8ToConsole('Введите количество элементов массива'));

readln(n);

SetLength(vector, n );

writeln(UTF8ToConsole('Введите '), n);

writeln(UTF8ToConsole('значений элементов массива')); for i:= 0 to n - 1 do read(vector[i]); bubble(vector);

writeln;

writeln(UTF8ToConsole('Отсортированный массив')); for i:= 0 to n - 1 do write(vector[i], ' '); writeln;

writeln(UTF8ToConsole('Нажмите любую клавишу'));

readkey;

end.

Алгоритм пузырьковой сортировки является одним из самых медленных. В

реализации алгоритма имеются два цикла. При первом выполнении внутренне-

го цикла будет выполнено n-1 сравнений, при втором n-2 сравнений и т.д. Всего будет выполнено n-1 таких циклов. Таким образом, всего будет выполнено

(n-1) + (n-2) + … + 1

сравнений. Выражение можно упростить:

n(n-1)/2 или (n2- n)/2

277

4.1 Алгоритмы сортировки

____________________________________________________________________

Таким образом, пузырьковая сортировка требует O(n2) сравнений. Количе-

ство перестановок для самого худшего случая, когда элементы массива отсор-

тированы в обратном порядке равно количеству сравнений, т.е. O(n2).

Имеется возможность небольшого улучшения алгоритма. Если во внут-

реннем цикле не происходит ни одной перестановки, то это означает, что мас-

сив уже отсортирован и дальнейшее выполнение алгоритма можно прекратить.

В наилучшем случае, когда входной массив уже отсортирован, алгоритму тре-

буется всего (n-1) сравнений и ни одной перестановки. К сожалению, в наи-

худшем случае, когда все элементы массива расположены в обратном порядке,

выигрыша во времени исполнения алгоритма не происходит. Приведем все-

таки реализацию этой модификации метода:

program modify_bubble_sort; uses

CRT, FileUtil; var

i, n: integer;

vector: array of integer;

{ ============= Сортировка методом "пузырька" ======== } procedure bubble(var vector: array of integer); var

temp: integer;

i, j, count: integer; perestanovka: boolean = false;

begin

count:= high(vector); for i:= 1 to count do begin

for j:= count downto i do

278

Глава 4 Типовые алгоритмы обработки информации

____________________________________________________________________

if vector[j - 1] > vector[j] then begin

perestanovka:= true; temp:= vector[j - 1]; vector[j - 1]:=vector[j]; vector[j]:= temp;

end;

if not perestanovka then break; end;

end; begin

writeln(UTF8ToConsole('Введите количество элементов массива'));

readln(n);

SetLength(vector, n );

writeln(UTF8ToConsole('Введите '), n);

writeln(UTF8ToConsole('значений элементов массива')); for i:= 0 to n - 1 do read(vector[i]); bubble(vector);

writeln;

writeln(UTF8ToConsole('Отсортированный массив')); for i:= 0 to n - 1 do write(vector[i], ' '); writeln;

writeln(UTF8ToConsole('Нажмите любую клавишу')); readkey;

end.

Существуют еще несколько модификаций и улучшений этого алгоритма.

При желании вы можете ознакомиться с ними в специальной литературе.

279

4.1 Алгоритмы сортировки

____________________________________________________________________

4.1.2 Сортировка выбором

Алгоритм сортировки выбором работает следующим образом: находим наименьший элемент в массиве и обмениваем его с элементом находящимся на первом месте. Затем ищем минимальный элемент без учета первого элемента и найденный минимальный элемент обмениваем со вторым элементом и так да-

лее. На i-м шаге выбираем наименьший из элементов a[i], ..., a[n] и меняем его местами с a[i]. После шага i, последовательность a[0],..., a[i] будет уже упоря-

доченной. Теперь ищем минимальный элемент среди a[i+1], ..., a[n] и меняем его с a[i+1]. Таким образом, на (n-1)-м шаге вся последовательность, кроме a[n]

оказывается отсортированной, а a[n] оказывается как раз там, где он и должен стоять, так как все меньшие элементы уже "ушли" влево. Этот метод называет-

ся сортировкой выбором, поскольку он на каждом следующем шаге алгоритма находит наименьший из оставшихся элементов массива и переставляет его сра-

зу в нужное место в массиве.

Количество сравнений для первого прохода равно n, для второго n-1 и т.д.

Общее количество сравнений равно n(n+1)/2 – 1, т.е. данный алгоритм требует

O(n2) сравнений. Количество же перестановок в этом алгоритме меньше, так как в каждом проходе он переставляет элементы только один раз и число пере-

становок составляет O(n). Таким образом, алгоритм выбора несколько эффек-

тивнее пузырькового метода. К тому же, алгоритм выбора является устойчи-

вым. Что это означает? Если среди элементов сортируемого объекта имеются одинаковые, то алгоритм не нарушает их взаимного расположения в исходном объекте. Пусть имеются две записи с одинаковыми ключами

1A

2B

1C

Рис. 4.5. Записи с одинаковыми ключами

280