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.
The 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.
one |
#include "stdafx.h" |
one |
program Bubble_Sort; |
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.
one |
for (i = 0; i { |
one |
for i: = 1 to N-1 do |
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 ).
Comments
To leave a comment
Algorithms
Terms: Algorithms