Сортировка массива пузырьком C

Самый известный алгоритм – пузырьковая сортировка (bubble sort, сортировка методом пузырька или просто сортировка пузырьком). Его популярность объясняется интересным названием и простотой самого алгоритма.

Алгоритм попарного сравнения элементов массива в литературе часто называют «методом пузырька», проводя аналогию с пузырьком, поднимающимся со дна бокала с газированной водой. По мере всплывания пузырек сталкивается с другими пузырьками и, сливаясь с ними, увеличивается в объеме. Чтобы аналогия стала очевидной, нужно считать, что элементы массива расположены вертикально друг над другом, и их нужно так упорядочить, чтобы они увеличивались сверху вниз.

Алгоритм состоит в повторяющихся проходах по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно, и если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, это означает – массив отсортирован. При проходе алгоритма элемент, стоящий не на своём месте, «всплывает» до нужной позиции.

#include <stdio.h>
#include <conio.h>
 
#define For(a,b) for (a=0 ; a<b ; a++)
 
void bubblesort (int a [] , int n)
{
    // I -> i :D
    int i, j , k;
     
    For(i , n)
    for (j = n - 1; j > i; j--)
        if (a [j - 1] > a [j ]) 
        {
            k = a[j - 1];
            a [j - 1] = a [j ] ;
            a [j ] = k ;
        }
}
void main()
{
    int tmp[5] = {0, 1, 5, 4, 3};
    bubblesort(tmp, 5);
     
    int i;
    For(i, 5)
        printf("%d", tmp[i]);
    getch();
}

В пузырьковой сортировке количество сравнений всегда одно и то же, поскольку два цикла for повторяются указанное количество раз независимо от того, был список изначально упорядочен или нет. Это значит, что алгоритм пузырьковой сортировки всегда выполняет

(n2−n)2

сравнений, где n – количество сортируемых элементов. Данная формула выведена на том основании, что внешний цикл выполняется n – 1 раз, а внутренний выполняется в среднем n / 2 раз.