Презентация на тему Сортировка обменом(Сортировка пузырьком)

алгоритм сортировки.
Эффективен он лишь для небольших массивов.
Недостатком является

высокая сложность алгоритма: O(n²).
Алгоритм считается учебным и практически не применяется вне учебной литературы, вместо него на практике применяются более эффективные алгоритмы сортировки.
В то же время метод сортировки обменами лежит в основе некоторых более совершенных алгоритмов, таких как шейкерная сортировка, пирамидальная сортировка и быстрая сортировка.
Алгоритм является устойчивым (не меняет взаимного расположения равных элементов).
Алгоритм не использует дополнительной памяти, т.е. все действия осуществляются на одном и том же массиве.

Преимущества и недостатки

За каждый проход элементы последовательно сравниваются попарно и, если

порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются N-1 раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При каждом проходе алгоритма по внутреннему циклу, очередной наибольший элемент массива ставится на своё место в конце массива рядом с предыдущим наибольшим элементом, а наименьший элемент перемещается на одну позицию к началу массива («всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма).

Описание

8» и отсортируем значения по возрастанию, используя сортировку пузырьком.

Выделены те элементы, которые сравниваются на данном этапе.

Пример работы алгоритма

Первый проход:
(5 1 4 2 8) (1 5 4 2 8)

(1 5 4 2 8) (1 4 5 2 8)
(1 4 5 2 8) (1 4 2 5 8)
(1 4 2 5 8) (1 4 2 5 8)
Второй проход:
(1 4 2 5 8) (1 4 2 5 8) (1 4 2 5 8) (1 2 4 5 8) (1 2 4 5 8) (1 2 4 5 8) (1 2 4 5 8) (1 2 4 5 8)

Здесь алгоритм сравнивает два первых элемента и меняет их местами.
Меняются местами 5 и 4, т. к. 5>4.
Меняются местами 5 и 4, т. к. 5>2.
Алгоритм не меняет местами элементы, т. к. 5<8.

Смена позиций не нужна т. к. 1<4.
Меняются местами, так как 4 > 2.
Смена позиций не нужна т. к. 4<5.
Смена позиций не нужна т. к. 1<4.

Теперь массив отсортирован, но алгоритм не знает так ли это. Поэтому ему необходимо сделать еще один полный проход и определить , что перестановок элементов больше не было.

n,x,i,j:integer;
begin clrscr;
writeln('Введите размер массива');
readln(n);
for i:= 1

to n do
begin
write('Введите ',i,'-й элемент массива ');
read(a[i]);
end;
writeln('Введенный массив:');
for i:= 1 to n do
write(a[i],' ');
writeln;

Код и результат выполнения программы

for j:=1 to n-1 do
begin
for i:=1 to n-1 do
if a[i]>a[i+1] then
begin
x:=a[i];
a[i]:=a[i+1];
a[i+1]:=x;
end;
end;
writeln('Отсортированный массив:');
for i:=1 to n do
write(a[i],' ');
readln;
end.