Bubble sorting is not only not considered the fastest method, moreover, it closes the list of the slowest methods of ordering. However, it has its advantages. So, sorting by the bubble method is the most logical and natural solution to the problem, if you need to arrange the elements in a certain order. An ordinary person manually, for example, will use it precisely - simply by intuition.
Where did such an unusual name come from?
The name of the method was invented using the analogy with air bubbles in water. This is a metaphor. Just as small air bubbles rise up - because their density is greater than any liquid (in this case, water), so each element of the array, the smaller it is in value, the more it gradually makes its way to the beginning of the list of numbers.
Algorithm description
Bubble sorting is performed as follows:
- first pass: elements of an array of numbers are taken in two and are also compared in pairs. If in some two elements the first value is greater than the second, the program will exchange them;
- therefore, the largest number falls at the end of the array. While all other elements remain, as they were, in a chaotic order and still require sorting;
- therefore, a second pass is needed: it is made by analogy with the previous (already described) and has a number of comparisons - minus one;
- the passage number three comparisons are one less than the second, and two, than the first. Etc;
- to summarize, each pass has (total values in the array, a specific number) minus (pass number) comparisons.
Even shorter, the algorithm of the future program can be written like this:
- an array of numbers is checked until any two numbers are found, the second of which must be greater than the first;
- program elements that are incorrectly positioned relative to each other are interchanged.
Pseudocode based on the described algorithm
The simplest implementation is as follows:
Sortirovka_Puzirkom procedure;
Start
loop for j from nachalnii_index to konechii_index ;
loop for i from nachalnii_index to konechii_index-1 ;
if massiv [i]> massiv [i + 1] (the first element is larger than the second), then:
(change values in places);
the end
Of course, here simplicity only exacerbates the situation: the simpler the algorithm, the more all the flaws appear in it. The time consuming is too large even for a small array (relativity comes into play: for a layman, the amount of time may seem small, but in the programmer’s business every second or even millisecond counts).
It took a better implementation. For example, taking into account the exchange of values in an array in places:
Sortirovka_Puzirkom procedure;
Start
sortirovka = true;
loop while sortirovka = true;
sortirovka = false;
loop for i from nachalnii_index to konechii_index-1 ;
if massiv [i]> massiv [i + 1] (the first element is larger than the second), then:
(swap elements);
sortirovka = true; (indicated that the exchange was made).
The end.
Disadvantages of the method
The main minus is the duration of the process. How long does the bubble sorting algorithm take ?
The execution time is calculated from the square of the number of numbers in the array - the final result is proportional to it.
In the worst case scenario, the array will be traversed as many times as there are elements in it minus one value. This is because ultimately there is only one element left that has nothing to compare with, and the last pass through the array becomes a useless action.
In addition, the method of sorting simple exchanges, as it is also called, is effective only for small arrays. It will not be possible to process large amounts of data with its help: the result will be either errors or a malfunction of the program.
Advantages
Bubble sorting is very easy to understand. In the curricula of technical universities when studying the ordering of the elements of the array, it is passed first. The method is easily implemented both in the Delphi programming language (D (Delphi) and C / C ++ (C / C plus plus), an incredibly simple algorithm for arranging values in the correct order and in Pascal (Pascal). Bubble sorting is ideal for beginners.
Due to deficiencies, the algorithm is not used for extracurricular purposes.
Clear sorting principle
The initial view of the array is 8 22 4 74 44 37 1 7
Step 1 8 22 4 74 44 37 1 7
8 22 4 74 44 1 37 7
8 22 4 74 1 44 37 7
8 22 4 1 74 44 37 7
8 22 1 4 74 44 37 7
8 1 22 4 74 44 37 7
1 8 22 4 74 44 37 7
Step 2 1 8 22 4 74 44 7 37
1 8 22 4 74 7 44 37
1 8 22 4 7 74 44 37
1 8 22 4 7 74 44 37
1 8 4 22 7 74 44 37
1 4 8 22 7 74 44 37
Step 3 1 4 8 22 7 74 37 44
1 4 8 22 7 37 74 44
1 4 8 22 7 37 74 44
1 4 8 7 22 37 74 44
1 4 7 8 22 37 74 44
Step 4 1 4 7 8 22 37 44 74
1 4 7 8 22 37 44 74
1 4 7 8 22 37 44 74
1 4 7 8 22 37 44 74
Step 5 1 4 7 8 22 37 44 74
1 4 7 8 22 37 44 74
1 4 7 8 22 37 44 74
Step 6 1 4 7 8 22 37 44 74
1 4 7 8 22 37 44 74
Step 7 1 4 7 8 22 37 44 74
Pascal bubble sort example
Example:
const kol_mas = 10;
var massiv: array [1..kol_mas] of integer;
a, b, k: integer;
begin
writeln ('input', kol_mas, 'elements of array');
for a: = 1 to kol_mas do readln (massiv [a]);
for a: = 1 to kol_mas-1 do begin
for b: = a + 1 to kol_mas do begin
if massiv [a]> massiv [b] then begin
k: = massiv [a]; massiv [a]: = massiv [b]; massiv [b]: = k;
end;
end;
end;
writeln ('after sort');
for a: = 1 to kol_mas do writeln (massiv [a]);
end.
An example of bubble sorting in C (C)
Example:
#include
#include
int main (int argc, char * argv [])
{
int massiv [8] = {36, 697, 73, 82, 68, 12, 183, 88}, i, ff;
for (;;) {
ff = 0;
for (i = 7; i> 0; i -) {
if (massiv [i] <massiv [i-1]) {
swap (massiv [i], massiv [i-1]);
ff ++;
}
}
if (ff == 0) break;
}
getch (); // screen delay
return 0;
}.