Этот простой алгоритм работает, меняя порядок соседних элементов, если они находятся в неправильном порядке (например, неправильный порядок 4,3; правильный порядок 3,4).
Представьте, что у нас есть массив a[4]={4,3,2,1}
- Основная идея заключается в том, что нам нужно поместить самый большой элемент в правильную позицию (последнюю позицию) a[4] = {3,4,2,1}
- a[4] = {3,2,4,1}
- a[4] = {3,2,1,4} — теперь самый большой элемент в нужном месте
теперь те же действия нужно проделать со вторым по величине элементом
4. a[4] = {2,3,1,4}
5. a[4] = {2,1,3, 4}
последний обмен здесь это [0] и [1]
6. a[4] = {1,2,3, 4}
Давайте посмотрим, как применить эту идею к программе на языке Си:
#include <stdio.h> void swap(int* a, int* b) { //a and b both pointers int save = *a; *a = *b; *b = save; } void bubble_sort(int a[]) { int indicator; //it can be 0 or 1 for (int i = 0; i < 10 - 1; i++) { indicator = 0; for (int j = 0; j < 10 - i - 1; j++) { if (a[j] > a[j + 1]) { /* check is in our array elements which is bigger that next element? ex. 4, 3. if yes, we need to sawp */ swap(&a[j], &a[j + 1]); indicator = 1; } } if (indicator == 0) //this means that all elements are swapped break; } for (int i=0; i<10; i++) { //output the array printf("%d ", a[i]); } } int main() { int a[10]; for (int i=0; i<10; i++) { //input the array scanf("%d", &a[i]); } bubble_sort(a); //call the function of sorting return 0; }
теперь у нас есть код ~ давайте посмотрим, как он работает
Как работает функция обмена?
В функции подкачки и «a», и «b» являются указателями. Сначала мы сохраняем значение «а» в новой переменной с именем «сохранить». Затем мы присваиваем значение «b» значению «a». Наконец, мы устанавливаем значение «b» в качестве значения «сохранить», которое является начальным значением «а».
Как работает функция bubble_sort?
Чтобы использовать функцию bubble_sort, мы передаем массив в качестве аргумента. Мы создаем переменную под названием «индикатор», которая может иметь значение 0 или 1. Затем у нас есть вложенные циклы.
Первый цикл повторяется 9 раз, и внутри этого цикла мы проверяем порядок элементов с помощью второго цикла. Внутри второго цикла мы определяем, правильный порядок элементов или нет. Если это не так, нам нужно поменять местами значения соседних переменных с помощью функции swap.
Чтобы порядок был правильным, условие должно быть «a[k] ‹ a[k+1]» (например, 3, 4). Если условие не выполняется и нужно поменять местами, значит «a[k] › a[k+1]» (например, 4, 3).
Кроме того, после замены элементов значение «индикатора» становится равным 1, что указывает на то, что нам нужно продолжить проверку порядка элементов. Только когда «a[j] › a[j + 1]» никогда не бывает истинным, мы можем прервать цикл и вывести массив с новым порядком элементов.
Кстати, мой пример алгоритма bubble_sort работает только для массива целых чисел длиной 10. Если вы хотите использовать его для массива неизвестной длины или другого типа переменных, вам просто нужно заменить «10» на «n» и передать массив и «n» в функцию bubble_sort или изменить тип переменных, если это необходимо. Я надеюсь, что мои заметки о пузырьковой сортировке будут полезными и понятными! ☺️