Sorting methods in programming: sorting by "bubble"

Sorting by a bubble is not only not considered the fastest method, moreover, it closes the list of the slowest ways of ordering. However, it also 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, for example, will use it by hand, simply by intuition.

Where did this unusual name come from?

The name of the method was invented using an analogy with air bubbles in water. This is a metaphor. Just as small air bubbles rise to the top - because their density is greater than any liquid (in this case - water), and 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.

Description of the algorithm

Bubble sorting is performed as follows:

• The first pass: the elements of the array of numbers are taken in two and are also compared in pairs. If in some two of the elements the first value is greater than the second, the program makes their exchange of places;
• Therefore, the largest number is at the end of the array. While all other elements remain, as they were, in a chaotic order and require further sorting;
• Therefore, a second pass is needed: it is produced by analogy with the previous one (already described) and has a number of comparisons - minus one;
• At the pass, the number three comparisons is one less than the second, and the deuce is two than the first. And so on;
• We summarize that each pass has (in the array, a specific number) minus (number of passes) comparisons.

Even shorter algorithm of the future program can be written as follows:

• The array of numbers is checked until two numbers are found, the second of which must be greater than the first;
• Incorrectly located in relation to each other elements of the array, the program swaps.

Pseudocode based on the described algorithm

The simplest implementation is as follows:

Procedure Sortirovka_Puzirkom ;

Start

A loop for j from nachalnii_index to konechii_index ;

A loop for i from nachalnii_index to konechii_index-1 ;

If massiv [i]> massiv [i + 1] (the first element is greater than the second), then:

(Change the values in places);

the end

Of course, here simplicity only exacerbates the situation: the simpler the algorithm, the more it shows all the shortcomings. Time-consuming is too great even for a small array (here comes the relativity: for the average person the amount of time may seem small, but in the programmer's every second or even milliseconds on the account).

It took a better implementation. For example, taking into account the exchange of values in the array in some places:

Procedure Sortirovka_Puzirkom ;

Start

Sortirovka = true;

Cycle while sortirovka = true;

Sortirovka = false;

A loop for i from nachalnii_index to konechii_index-1 ;

If massiv [i]> massiv [i + 1] (the first element is greater than the second), then:

(We change the elements in places);

Sortirovka = true; (Indicated that the exchange was made).

The end.

Disadvantages of the method

The main disadvantage is the duration of the process. How long does the bubble sort algorithm work ?

The execution time is calculated from the square of the number of numbers in the array - the final result is proportional to it.

With the worst-case scenario, the array will be traversed as many times as there are elements in it, minus one value. This is because in the end there is only one element that has nothing to compare with, and the last pass through the array becomes a useless action.

In addition, the method of sorting by simple exchanges, as it is also called, is effective only for arrays of small size. Large amounts of data can not be processed using it: the result will be either errors, or a program crash.

Advantages

Sorting a bubble is very easy to understand. In the curricula of technical universities, when studying the ordering of elements of an array, it passes 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 for Pascal (Pascal) .The sorting with a bubble is ideal for beginners.

Due to shortcomings, the algorithm is not used for extracurricular purposes.

A clear principle of sorting

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

Example of sorting by a bubble in Pascal

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.

Example of sorting by a bubble 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]

Swap (massiv [i], massiv [i-1]);

Ff ++;

}

}

If (ff == 0) break;

}

Getch (); // screen delay

Return 0;

}.