Bubble sort

Lecture



Bubble sorting (exchange sorting) is an easy-to-implement and inefficient sorting algorithm. The method is studied one of the first on the course of the theory of algorithms, while in practice it is used very rarely.

Bubble sort T Bubble sort he idea of ​​the algorithm is as follows. Neighboring elements of the sequence are compared with each other and, if necessary, are interchanged. As an example, consider the ordering by the bubble sorting method of an array, the number of elements N of which is 5: 9, 1, 4, 7, 5. As a result, you should get an array with elements arranged in ascending order of their values ​​(see fig.).

First, the first two elements of the sequence are compared: 9 and 1. Since the value of the first element is greater than the value of the second, i.e. 9> 1, they are swapped. Next, the second and third elements are compared: nine is more than four, therefore, the elements exchange positions again. Similarly, the algorithm continues to run until all elements of the array are in place. In total, this will require N * (N-1) comparisons. In particular, 20 comparisons were made on this sequence and only 5 permutations.

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

Bubble sort

C ++ program code:

one
2
3
four
five
6
7
eight
9
ten
eleven
12
13
14
15
sixteen
17
18
nineteen
20
21
22
23
24
25
26
27
28
29
thirty
31
32

#include "stdafx.h"
#include
using namespace std;
int i, j, count, key;
void BubbleSort (int A [], int N) // sort by bubble
{
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 << "Result array:";
for (i = 0; i }
void main ()
{
setlocale (LC_ALL, "Rus");
int N; int A [1000];
cout << "Number of elements>"; cin >> N;
for (i = 0; i {cout << i + 1 << "element>"; cin >> A [i]; }
BubbleSort (A, N);
system ("pause >> void");
}

Pascal program code:

one
2
3
four
five
6
7
eight
9
ten
eleven
12
13
14
15
sixteen
17
18
nineteen
20
21
22
23
24
25
26
27
28
29
thirty
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); {bubble sort}
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 ('Resulting array:');
for i: = 1 to n do write (A [i], ''); {array output}
end;
{main program block}
begin
clrscr;
write ('Number of elements>'); read (N);
for i: = 1 to N do {input array}
begin write (i, 'element>'); read (A [i]); end;
BubbleSort (A, N);
readkey;
end.

The above code can be improved, namely, to halve the number of comparisons performed. For this, it is sufficient with each step i of the outer loop on i to reduce the number of iterations of the inner loop. Below is the main fragment of the exchange sorting algorithm for C ++ and Pascal, its improved version.

C ++:

one
2
3
four
five
6
7
eight
9
ten
eleven
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:

one
2
3
four
five
6
7
eight
9
ten
eleven
12
13

for i: = 1 to N-1 do
begin
for j: = 1 to Ni 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;

As noted, the algorithm is rarely used in practice because it has low performance. At best, bubble sorting will take O (n) time, and on average, and worst, O (n 2 ).

created: 2014-11-30
updated: 2021-01-10
132597

Rating 9 of 10. count vote: 2
Are you satisfied?:

Comments

ОЛЬГА
30-09-2021
Спасибо КОД отличный, РАБОТАЕТ! спасибо!!
To leave a comment
If you have any suggestion, idea, thanks or comment, feel free to write. We really value feedback and are glad to hear your opinion.
To reply

Algorithms

Terms: Algorithms