Сортировка пузырьком (обменная сортировка) – простой в реализации и малоэффективный алгоритм сортировки. Метод изучается одним из первых на курсе теории алгоритмов, в то время как на практике используется очень редко.
Идея алгоритма заключается в следующем. Соседние элементы последовательности сравниваются между собой и, в случае необходимости, меняются местами. В качестве примера рассмотрим упорядочивание методом пузырьковой сортировки массива, количество элементов N которого равно 5: 9, 1, 4, 7, 5. В итоге должен получиться массив с элементами, располагающимися в порядке возрастания их значений (см. рис.).
Вначале сравниваются два первых элемента последовательности: 9 и 1. Так как значение первого элемента больше значения второго, т. е. 9>1, они меняются местами. Далее сравниваются второй и третий элементы: девятка больше четверки, следовательно, элементы снова обмениваются позициями. Аналогично алгоритм продолжает выполняться до тех пор, пока все элементы массива не окажутся на своих местах. Всего для этого потребуется N*(N-1) сравнений. В частности, на данной последовательности произведено 20 сравнений и только 5 перестановок.
Код программы на 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 <iostream> using namespace std; int i, j, count, key; void BubbleSort(int A[], int N) //сортировка пузырьком { for (i=0; i<N; i++) { for (j=0; j<N-1; j++) { key=j+1; count=A[key]; if (A[j]>A[key]) { A[key]=A[j]; A[j]=count; } } } cout<<"Результирующий массив: "; for (i=0; i<N; i++) cout<<A[i]<<" "; //вывод массива } void main() { setlocale(LC_ALL, "Rus"); int N; int A[1000]; cout<<"Количество элементов > "; cin>>N; for (i=0; i<N; i++) //ввод массива { cout<<i+1<<" элемент > "; 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. |
C++:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
for (i=0; i<N-1; i++) { for (j=0; j<N-(i+1); 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; |
Похожие записи:
У меня в паскале почему то выдает ошибку, может она действительно есть в коде?
Может и есть, только было бы не плохо увидеть сам код)