Sorting Methods in Programming: Bubble Sorting

Bubble sorting is not only not considered the mostfaster method, moreover, it closes the list of the slowest methods of ordering. However, it has its advantages. So, bubble sorting is the most logical and natural solution to a problem, if you need to arrange the elements in a certain order. An ordinary person manually, for example, will take advantage of him - just by intuition.

Where did this unusual name come from?

The name of the method was invented using the analogy withair bubbles in the 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), so is each element of the array; the smaller it is in value, the more it gradually makes its way to the top of the list of numbers.

Description of the algorithm

Sorting bubble is as follows:

• first pass: elements of an array of numbers are taken in two and are also compared in pairs. If in some kind of two elements the first value is greater than the second, the program makes their exchange of places;
• therefore, the largest number goes to the end of the array. While all other elements remain, as they were, in a chaotic order and require more sorting;
• therefore, a second pass is necessary: ​​it is produced by analogy with the previous (already described) and has the number of comparisons - minus one;
• at passage number three comparisons are one less than the second, and two more than the first. And so on;
• to summarize, each pass has (total values ​​in the array, a specific number) minus (number of pass) comparisons.

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

• The array of numbers is checked until any 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 Sort_Bubble;

Start

cycle for f from starting_index before end_index;

cycle for and from starting_index before final_index-1;

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

(swapping values);

the end

Of course, here simplicity only aggravatessituation: the simpler the algorithm, the more all the flaws appear in it. The cost of time is too great even for a small array (here relativity comes into play: for a layman, the amount of time may seem small, but in the programmer's case every second or even millisecond is counted).

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

Procedure Sort_Bubble;

Start

sorting = truth;

cycle bye sorting = truth;

sorting = false;

cycle for and from starting_index before final_index-1;

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

(swap elements);

sorting = truth; (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 sorting algorithm run?

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

In the worst case, the array will be passed.as many times as there are elements in it minus one value. This happens because, ultimately, there is only one element left that cannot be compared with anything, and the last pass through the array becomes a useless action.

In addition, a simple sorting method is effective.exchanges, as they are called, only for small-sized arrays. It will not be possible to process large amounts of data with it: the result will be either errors or program failure.

Advantages

Bubble sorting is very easy to understand.In the curricula of technical universities in the study of the ordering of the elements of the array it is held in the first place. The method is easily implemented in both 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 Pascal (Pascal). Bubble sorting is ideal for beginners.

Because of the shortcomings, the algorithm is not used for extracurricular purposes.

Clear sorting principle

The initial appearance 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 Sample 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 sorting 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;

}.