Сортировка пузырьком кратко

Лекция

Привет, сегодня поговорим про сортировка пузырьком, обещаю рассказать все что знаю. Для того чтобы лучше понимать что такое сортировка пузырьком , настоятельно рекомендую прочитать все из категории Алгоритмы и теория алгоритмов.

сортировка пузырьком (обменная сортировка) – простой в реализации и малоэффективный алгоритм сортировки. Метод изучается одним из первых на курсе теории алгоритмов, в то время как на практике используется очень редко.

Сортировка пузырьком Идея алгоритма заключается в следующем. Соседние элементы последовательности сравниваются между собой и, в случае необходимости, меняются местами. В качестве примера рассмотрим упорядочивание методом пузырьковой сортировки массива, количество элементов N которого равно 5: 9, 1, 4, 7, 5. В итоге должен получиться массив с элементами, располагающимися в порядке возрастания их значений (см. рис.).

Вначале сравниваются два первых элемента последовательности: 9 и 1. Так как значение первого элемента больше значения второго, т. е. 9>1, они меняются местами. Далее сравниваются второй и третий элементы: девятка больше четверки, следовательно, элементы снова обмениваются позициями. Аналогично алгоритм продолжает выполняться до тех пор, пока все элементы массива не окажутся на своих местах. Всего для этого потребуется N*(N-1) сравнений. В частности, на данной последовательности произведено 20 сравнений и только 5 перестановок.

Блок-схема алгоритма приведена на рисунке 3.

Сортировка пузырьком

Код программы на C++:

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

#include "stdafx.h"
#include
using namespace std;
int i, j, count, key;
void BubbleSort(int A[], int N) //сортировка пузырьком
{
for (i=0; i{
for (j=0; j{
key=j+1;
count=A[key];
if (A[j]>A[key])
{
A[key]=A[j];
A[j]=count;
}
}
}
cout<<"Результирующий массив: ";
for (i=0; i}
void main()
{
setlocale(LC_ALL, "Rus");
int N; int A[1000];
cout<<"Количество элементов > "; cin>>N;
for (i=0; i{ cout< "; cin>>A[i]; }
BubbleSort(A, N);
system("pause>>void");
}

Код программы на Pascal:

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

program Bubble_Sort;
uses crt;
type arr=array[1..1000] of integer;
var A: arr;
N, i, j: integer;
procedure BubbleSort(A: arr; N: integer); {сортировка пузырьком}
var key, count: integer;
begin
for i:=1 to N do
begin
for j:=1 to N-1 do
begin
key:=j+1;
count:=A[key];
if A[j]>A[key] then
begin
A[key]:=A[j];
A[j]:=count;
end
end
end;
write('Результирующий массив: ');
for i:=1 to n do write(A[i],' '); {вывод массива}
end;
{основной блок программы}
begin
clrscr;
write('Количество элементов > '); read(N);
for i:=1 to N do {ввод массива}
begin write(i, ' элемент > '); read(A[i]); end;
BubbleSort(A, N);
readkey;
end.

Приведенный код можно улучшить, а именно – вдвое уменьшить количество выполняемых сравнений. Об этом говорит сайт https://intellect.icu . Для этого достаточно с каждым шагом i внешнего цикла на i уменьшать количество итераций внутреннего цикла. Ниже показан основной фрагмент алгоритма обменной сортировки для языков C++ и Pascal, его улучшенный вариант.

C++:

1
2
3
4
5
6
7
8
9
10
11
12
13

for (i=0; i{
for (j=0; j{
key=j+1;
count=A[key];
if (A[j]>A[key])
{
A[key]=A[j];
A[j]=count;
}
}
}

Pascal:

1
2
3
4
5
6
7
8
9
10
11
12
13

for i:=1 to N-1 do
begin
for j:=1 to N-i do
begin
key:=j+1;
count:=A[key];
if A[j]>A[key] then
begin
A[key]:=A[j];
A[j]:=count;
end
end
end;

Как отмечалось, алгоритм редко используется на практике, поскольку имеет низкую производительность. В лучшем случае сортировка пузырьком потребует O(n) времени, а в среднем и худшем – O(n2).

На этом все! Теперь вы знаете все про сортировка пузырьком, Помните, что это теперь будет проще использовать на практике. Надеюсь, что теперь ты понял что такое сортировка пузырьком и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Алгоритмы и теория алгоритмов

Из статьи мы узнали кратко, но содержательно про сортировка пузырьком

Сортировка пузырьком кратко

Код программы на C++:

Код программы на Pascal:

C++:

Pascal:

Комментарии

Оставить комментарий

Алгоритмы и теория алгоритмов

Термины: Алгоритмы и теория алгоритмов