Пузырьковая сортировка - сортировка обменом
Пузырьковый метод наиболее распространенный. Он требует минимального объема памяти, но затраты времени велики.
Дано n чисел, которые необходимо расположить по возрастанию.
Алгоритм пузырьковой сортировки:
1) числа сравниваются попарно: первое со вторым; второе с третьим; i-тое – с (i+1) - тым;
2) если меньшее стоит в паре на втором месте (числа в паре не упорядочены по возрастанию), то сравниваемые числа меняются местами.
За один просмотр минимальное число "вытолкнется", по крайней мере, на одно место вперед, а максимальное – переместится в самый конец, т.е. минимальное число как легкий пузырек воздуха в жидкости постепенно "всплывает" в начало последовательности. Отсюда– название метода. За n-1 просмотр произойдет полное упорядочение массива при любом исходном расположении чисел в н
Пример. Пузырьковая сортировка
Дано n чисел, которые необходимо расположить по возрастанию.
Алгоритм пузырьковой сортировки:
1) числа сравниваются попарно: первое со вторым; второе с третьим; i-тое – с (i+1) - тым;
2) если меньшее стоит в паре на втором месте (числа в паре не упорядочены по возрастанию), то сравниваемые числа меняются местами.
За один просмотр минимальное число "вытолкнется", по крайней мере, на одно место вперед, а максимальное – переместится в самый конец, т.е. минимальное число как легкий пузырек воздуха в жидкости постепенно "всплывает" в начало последовательности. Отсюда– название метода. За n-1 просмотр произойдет полное упорядочение массива при любом исходном расположении чисел в н
Пример. Пузырьковая сортировка
Program Sort;
Const
Nmax = 100;
Var
X : Array [1..Nmax] Of Real;
A : Real;
n, k, i : Integer;
Begin
Writeln('Введите количество чисел');
Readln(n);
Writeln('Введите массив чисел');
For i := 1 To n Do
Read (X[i]);
{ Сортировка }
For k := 1 To n-1 Do
For i := 1 To n-1 Do
If X[i] > X[i+1] Then
Begin
A:=X[i];
X[i]:=X[i+1];
X[i+1]:=A
End;
Writeln('Отсортированный массив чисел:');
For i:=1 To n Do
Write (X[i]);
End.
Пример. Ускоренная пузырьковая сортировка
Program SortUsk;
Const
Nmax = 100;
Var
X : Array [1..Nmax] Of Real;
A : Real;
P : Boolean;
L, K, I, N : Integer;
Begin
Writeln('Введите количество чисел');
Readln(n);
Writeln('Введите массив чисел');
For i := 1 To n Do
Read(X[i]);
P := True; {Перестановка есть}
K := 1; {Номер просмотра}
While P Do
Begin
L:=0; {Кол. перестановок}
For i := 1 To n-k Do
If X[i] > X[i+1] Then
Begin
A := X[i];
X[i]:=X[i+1];
X[i+1]:=A;
L:=L+1
End;
If L=0 Then
P:=False;
k:=k+1;
End;
Writeln('Отсортированный массив чисел');
For i := 1 To n Do
Write(X[i]);
End.
