Сортировка пузырьком на С: примеры и объяснения алгоритма

Сортировка пузырьком (Bubble Sort) – это один из простейших алгоритмов сортировки, который работает путем сравнения и обмена соседних элементов. Он получил свое название из-за того, что на каждой итерации наибольший элемент "всплывает" в конец массива, как пузырек в воде.

Пример кода на языке C++:

cpp
#include 
using namespace std;
void bubbleSort(int arr[], int n){
    for(int i=0; iarr[j+1]){
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}
int main(){
    int arr[] = {5, 2, 9, 3, 8, 4};
    int n = sizeof(arr)/sizeof(arr[0]);
    
    bubbleSort(arr, n);
    
    for(int i=0; i

В этом примере мы используем вложенные циклы для сравнения каждого элемента с каждым другим. Если текущий элемент больше следующего, то мы меняем их местами. После прохода внутреннего цикла наибольший элемент "всплывает" в конец массива. После каждой итерации внешнего цикла мы уменьшаем количество элементов, которые нужно сравнивать, на 1.

Сложность сортировки пузырьком для худшего случая (когда массив уже отсортирован в обратном порядке) составляет O(n^2). Однако, в лучшем случае (когда массив уже отсортирован) и среднем случае сложность составляет O(n), что делает этот алгоритм эффективным для небольших массивов данных.