The sorting algorithm array “bubble sorting” seen in virtually all textbooks on programming in c++. It is easy to understand for beginners. It is an intuitive and extremely simple.
In practice, this algorithm is almost nobody uses, because it is slow and there are faster and more advanced algorithms. We also analyze it because, that sorting “bubble” – it is the basis of some of the more efficient algorithms, which will be described in the following articles. This“fast” sorting, “pyramidal” sorting and “shaker” sorting.
How does it work “bubble” sorting? Suppose we have unsortedarray numbers of 5 elements and we have to put the values in ascending order. For clarity, below depict the array vertically “Source array”.
Sorting algorithm “bubble” is repeated passes through the array using nested loops. With each pass through the array are compared between a pair “neighbouring” elements. If the number of some of the compared pairs are arranged in the correct order – going on exchange (overwrite) the values of the array of cells.
Figuratively speaking, in our example 2 “easier” than 3 – so the exchange has, next 2 “easier” than 7 – again exchange, etc.. In comparing the zero and the first element in our drawing no exchange, as 2 “heavier” than 1. Thus a “easy” value, as a bubble in water, rises to the desired position. That's why the name of the algorithm.
Consider a sorting algorithm “bubble” in the work:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 | #include <iostream> using namespace std; // прототип функции, которая выполнит сортировку "пузырьком" void bubbleSort(int arrForSort[], const int SIZE); void main() { setlocale(LC_ALL, "rus"); const int SIZE = 5; int arr[SIZE]; cout << "Исходный массив:\n"; for (int i = 0; i < SIZE; i++) { arr[i] = SIZE - i; // заполняем значениями по убыванию cout << arr[i] << "\n__\n"; } cout << "\n\n"; bubbleSort(arr, SIZE); // передаем в функцию для сортировки cout << "Массив после сортировки:\n"; for (int i = 0; i < SIZE; i++) { cout << arr[i] << "\n__\n"; } cout << "\n\n"; } void bubbleSort(int arrForSort[], const int SIZE) { int buff = 0; // для временного хранения значения, при перезаписи for (int i = 0; i < SIZE - 1; i++) // { // вложенный цикл проходит от четвертого элемента // до первого, находит с помощью if самое "легкое" значение, // сравнивая соседние пары элементов, // и поднимает его в нулевую ячейку массива for (int j = SIZE - 1; j > i; j--) { if (arrForSort[j] < arrForSort[j - 1]) { buff = arrForSort[j - 1]; arrForSort[j - 1] = arrForSort[j]; arrForSort[j] = buff; } } // далее значение i увеличивается на 1 // и внутренний цикл будет перебирать элементы // от четвертого до второго. Таким образом поднимет самое // "легкое" значение из оставшихся в первую ячейку и т.д. } } |
Carefully reviewing the example with detailed comments, you should be all clear. The result on the screen such:
You can add the following: after, as the inner loop runs once, the minimum value of the array will take a zero cell. Therefore, when repeated passage, the next minimum value of the remaining will have to be placed in the next cell (i + 1).
Thus there is no need to compare all interconnected elements of the array and again decreases the number of processed values for 1. When sorting “bubble” you need to pass SIZE – 1 iterations of the outer loop, so how to compare one item with itself – makes no sense.
Let us not forget that, what we said at the very beginning – algorithm “bubble” sorting is inefficient and slow. If we have a partially sorted array and you want to move to the top of only one value, it will still go through all the loops of iteration. That is, to make a comparison already sorted array of values, although it is already possible and do.
Let's improve this situation. Add another variable in the code-“flag”, that will give to know, whether there was an exchange of values in a given iteration of the outer loop or not. Before, How to log into the inner loop, “flag” will be dropped in 0.
If the exchange values in this loop happen – “flags” will be set to 1, if not – it will be equal to 0. In the latter case, (if “flag” is 0) – there were no exchanges and an array of fully sorted. Therefore, the program can exit the loop early, so as not to waste time on unnecessary follow-up comparisons.
Consider the following example:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 | #include <iostream> using namespace std; void bubbleSort(int arrForSort[], const int SIZE); int main() { setlocale(LC_ALL, "rus"); const int SIZE = 5; int arr[SIZE] = {3, 4, 2, 5, 6}; cout << "Исходный массив:\n"; for (int i = 0; i < SIZE; i++) { cout << arr[i] << "\n__\n"; } cout << "\n\n"; bubbleSort(arr, SIZE); cout << "Массив после сортировки:\n"; for (int i = 0; i < SIZE; i++) { cout << arr[i] << "\n__\n"; } cout << "\n\n"; return 0; } void bubbleSort(int arrForSort[], const int SIZE) { int buff = 0; int f; // "флаг" for (int i = 0; i < SIZE - 1; i++) { f = 0; for (int j = SIZE - 1; j > i; j--) { if (arrForSort[j] < arrForSort[j - 1]) { buff = arrForSort[j - 1]; arrForSort[j - 1] = arrForSort[j]; arrForSort[j] = buff; /* если хоть одна пара значений былы расположена неправильно то есть условие if - верно, то присваиваем флагу значение 1*/ f = 1; } } // если массив отсортирован и замен не было // то есть f осталось равным 0 - прерываем цикл if (f == 0) break; // для себя показываем количество проходов по массиву вложенным циклом cout << i + 1 << "!!! \n"; } cout << endl; } |
We see a picture after starting:
It can be seen that the program was nested loop through the array 1 times, shifted value 2 in the right place and completed work. And here, that will be on the screen, if you comment out all strings of code, where is a variable-“flag”:
The program empty 4 fold “drove” the array, although the value of 2 moved into the desired cell has the first pass nested loop.
The network has a cool video (author: AlgoRythmics). It presents “bubble” sorting an improved version (when sorted array elements are not compared with each other). Only – in our examples, compare values began with the last element. And as proposed, – from zero to the last. Look and see, as elements in the array are moved to the right places :)
good afternoon.
Help, please understand the method, racking their brains can not understand the principle of two nested loops.
There is a code:
#include
#include
using namespace std;
int main()
{
setlocale(LC_ALL, “Russian”);
int nums[10];
int a,b,t;
int size;
size = 10; // Number of items to be sorted.
// We put an array of random numbers.
for(t=0; t<size; t++) nums[t] = rand();
// Displays the original array.
cout << "Исходный массив:\n ";
for(t=0; t<size; t++) cout << nums[t] << ' ';
cout << '\n';
//The implementation of bubble sort algorithm.
for(a=1; a =; b–) {
if(nums[b-1] > nums[b]) { // If the values of the array elements
// We are not in order,
// then rearrange them.
t = nums[b-1];
nums[b-1] = nums[b];
nums[b] = t;
}
}
// Display the sorted array.
cout << "\n Отсортированный массив:\n ";
for(t=0; t<size; t++) cout << nums[t] << ' ';
system("pause");
return 0;
}
Interested:
for(a=1; a =; b–) {
if(nums[b-1] > nums[b]) { // If the values of the array elements
// We are not in order,
// then rearrange them.
t = nums[b-1];
nums[b-1] = nums[b];
nums[b] = t;
}
}
Why in a for loop(a=1; a<size; a++) a<siz а не a=a; b–) I can not tell.
And last
t = nums[b-1];
nums[b-1] = nums[b];
nums[b] = t;
Is it possible to somehow simplify the replacement?
good afternoon.
Help, you are welcome, to understand the method. head to break, can not understand.
There is a code with books:
#include
#include
using namespace std;
int main()
{
setlocale(LC_ALL, “Russian”);
int nums[10];
int a,b,t;
int size;
size = 10; // Number of items to be sorted.
// We put an array of random numbers.
for(t=0; t<size; t++) nums[t] = rand()%100;
// Displays the original array.
cout << "Исходный массив:\n ";
for(t=0; t<size; t++) cout << nums[t] << ' ';
cout << '\n';
//The implementation of bubble sort algorithm.
for(a=1; a =; b–) {
if(nums[b-1] > nums[b]) { // If the values of the array elements
// We are not in order,
// then rearrange them.
t = nums[b-1];
nums[b-1] = nums[b];
nums[b] = t;
}
}
// Display the sorted array.
cout << "\n Отсортированный массив:\n ";
for(t=0; t<size; t++) cout << nums[t] << ' ';
system("pause");
return 0;
}
Most care nested loops:
for(a=1; a =; b–)
The outer loop is why a<size rather than a = a what it is and how it works?
And last:
Prompt, how to persuade permutation:
t = nums[b-1];
nums[b-1] = nums[b];
nums[b] = t;
> Prompt, how to simplify the permutation:
And what is there to simplify?
The C, C ++ and similar languages (Pascal, Java, and others.) exchange values of 2 variables (a and b) only alternation third intermediate variable (c):
c = a;
a = b;
b = c; // а и b поменялись значениями
In a high-level languages, such as Python or Go, it would be easier to write:
a, b = b, a
It could be facilitated by faculty tsyi swap() ;
swap(arrForSort[j],arrForSort[j-1]);
It can be written in terms of the function swap() … Only this can hardly be considered a simplification, because it is the same in this function.
but at least it is not necessary to enter 3 variable
What's the difference ? … from one extra variable…
When it will go on quite elementary tasks in a more or less thorough, then one or two dozen variables more or less – cease to play a role. There come into play other criteria.
About the bubble sort algorithm would still need to remember that, what is it worst (in terms of efficiency, number of operations) sorting algorithm of all well-known.
But the interviews applicants and students in exams stubbornly “drags” this method.
In this there is some mystery…
Yes, it is a habit common. The method is the easiest-to-understand, that's all it drags.