Bubble Sort

Buble sort je nejjednodušší a intuitivní způsob, jak mozek přemýšlet o třídění. Zároveň je však nejméně efektivní. Při třídění bubláním procházíme pole a porovnáváme každý index se sousedním. Řazení probíhá probubláváním větších prvků doprava.

Princip

  • Postupně zleva doprava se porovnávají sousední dvojice prvků a pokud jsou prvky v nesprávném pořadí, prohodí se.
  • Tím se největší prvek dostane na poslední místo.
  • Celý postup se opakuje (n−1)-krát: pokaždé se seřazená podposloupnost vpravo prodlouží o jednu pozici doleva.
  • Pokud se během jednoho průchodu neprohodila žádná dvojice,už se nikdy žádná neprohodí a řazení skončilo.
  • Vhodný algoritmus, pokud je např. vstupní posloupnost z velké části seřazená.

Pseudokód

Vstup: pole P[1 … n]
Výstup: vzestupně seřazené pole P
Algoritmus BubbleSort
end := n
zmena := 1
Dokud zmena = 1:
  zmena := 0
  Pro j:= 1 … (end−1):
      Pokud P[j] > P[j+ 1]:
          Prohoď P[j] a P[j+ 1]
          zmena:= 1
  end--

Složitost

Korektně seřadí n-prvkové pole v čase O(n2) a je stabilní, in-place, datově citlivý.

Důkaz
  • Invariant: nejpozději po i-té iteraci cyklu na řádcích (3)–(9) se i-tý největší prvek pole dostane do P[n−i+1].
  • Protože všechny prvky od pozice n−i+1 doprava jsou již „na svých místech“ (tudíž pravý úsek P[n−i+1 … n] je vzestupně seřazen) a všechny před ním jsou menší, už na této pozici zůstane.
  • Iterací je tedy nejvýšen, každá trvá O(n) kroků, což dává časovou složitost O(n2).
  • Podmínka na řádku (6) zabrání prohození stejných prvků.

Implementace v C

void bubbleSort(int n, int a[]) {
    int i, s;

    do {
        s = 0;
        for (i=1; i<n; i++) {
            if (a[i-1]>a[i]) {
                swap(&a[i-1], &a[i]);
                s++;
            }
        }
        n--;
    } while (s);
}

Celý kód ke stažení zde.

Související