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 PAlgoritmus 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);
}