Sortowanie bąbelkowe to prosty algorytm sortowania o złożoności O(n2).

Niestety jest to algorytm mało wydajny, można nim posortować max tablice 1000 elementową.

Sortowanie to polega na porównywaniu dwóch sąsiednich liczb zaczynając od końca.

Wyobraź sobie pionowe ułożenie sortowanych elemntów i poddanie ich "sile wyporu": elementy "lżejsze" ( czyli te liczby mniejsze ) są wówczas "wypierane" do góry przez elementy "cięższa". Fizycznie wygląda to tak, że poruszamy się od "dna" ku górze i każdorazowo, gdy napotkamy taką parę sąsiadujących elementów, że element lżejszy  położony jest niżej, zamieniamy te elementy miejscami.

Przykładowa tablica o elementach [3, 9, 5, 2, 4].

Zaczynamy od ostatniego elementu i sprawdzamy czy jest on mniejszy od poprzedniego. W tym przypadku 4>2 więc porównujemy
następną parę. 2<5 a więc zamieniamy je miejscami ([3, 9, 2, 5, 4]). Sprawdzamy kolejną parę - 9 i 2.
Ich kolejność jest "zła" więc zamieniamy ([3, 2, 9, 5, 4]). Ostatnia para także jest w złej kolejności.
Tablica w tym momencie wygląda następująco [2, 3, 9, 5, 4].

Zaczynamy sprawdzanie od początku (tym razem już jednak nie sprawdzamy ostatniej pary). Tablica będzie kolejno zmieniać się:
[2, 3, 9, 4, 5] -> [2, 3, 4, 9, 5] -> [2, 3, 4, 9, 5]

[2, 3, 4, 5, 9] -> [2, 3, 4, 5, 9]

[2, 3, 4, 5, 9].

Proste prawda??

Teraz czas na implementację w C++:

void bubbleSort(int *tab, int size)  // *tab to wskaźnik, który przechowuje liczby do posortowania a size to rozmiar tablicy
{

// Tworzymy 2 pętle for w których:
   for(int i=1; i<rozmiar ;++i)// Wybieramy liczbę ostatnią i..
      for(int j=size-1; j>=i ;--j) // Liczbę obok

        // jeżeli liczba jest mniejsza od liczby obok to...
         if(tab[j] < tab[j-1]) {

           // Zamieniamy
            int tmp = tab[j];
            tab[j]=tab[j-1];
            tab[j-1]=tmp;
         }
}