Bubble Sort

Bubble Sort

Bubble sort je jednoduchý řadicí algoritmus, který slouží k seřazení prvků v poli. Jeho základní myšlenkou je postupně procházet pole a vždy porovnávat sousední prvky. Pokud je prvek na následující pozici menší než prvek na aktuální pozici, dojde k jejich výměně. Tímto způsobem se postupně "vynořují" největší prvky na konec pole.

Bubble sort je relativně jednoduchý na implementaci, ale není zrovna efektivní pro velká pole, protože vyžaduje kvadratický počet porovnání a výměn. Nicméně, je vhodný pro malá pole nebo pole, která již jsou téměř seřazená.

Základní popis fungování bubble sortu:

1. Porovnání: Algoritmus prochází pole zleva doprava a porovnává vždy dvě sousední čísla.

2. Výměna: Pokud je levé číslo větší než pravé, vymění si místa. Pokud jsou ve správném pořadí, nic se neděje.

3. Probublání: Tímto průchodem se zaručeně největší číslo dostane na úplný konec pole (na svou finální pozici).

4. Opakování: Celý proces se opakuje pro zbylou část pole (bez posledního, již seřazeného prvku).

5. Konec: 

   • Algoritmus končí buď po n-1 průchodech (n je velikost pole), nebo

   • končí, když během celého jednoho průchodu nedojde k žádné výměně (pole je seřazené).

Konkrétní příklad:

Mějme pole: [5, 1, 4, 2, 8]

1. průchod:

• 5 vs 1 → 5 je větší, výměna: [1, 5, 4, 2, 8]

• 5 vs 4 → 5 je větší, výměna: [1, 4, 5, 2, 8]

• 5 vs 2 → 5 je větší, výměna: [1, 4, 2, 5, 8]

• 5 vs 8 → 8 je větší, bez změny.

Výsledek: 8 je na konci ("probublala" na konec pole).

2. průchod

• 1 vs 4 → 1 je menší, bez změny. (Pole: [1, 4, 2, 5, 8])

• 4 vs 2 → 4 je větší, výměna. (Pole: [1, 2, 4, 5, 8])

• 4 vs 5 → 5 je větší, bez změny.

• (S osmičkou už neporovnáváme).

Výsledek po 2. průchodu: [1, 2, 4, 5, 8]

3. průchod

• 1 vs 2 → 1 je menší, bez změny. (Pole: [1, 2, 4, 5, 8])

• 2 vs 4 → 4 je větší, bez změny.

• (S pětkou a osmičkou už neporovnáváme).

Výsledek po 3. průchodu: [1, 2, 4, 5, 8]

Zde vidíme, že v celém průchodu nedošlo k žádné výměně a je proto možné skončit. Pokud ale používáme „hloupější“ variantu bubble sort, tak dojde ještě ke 4. průchodu.

4. průchod

• 1 vs 2 → 1 je menší, beze změny.

• (Se čtyřkou, pětkou a osmičkou už neporovnáváme).

Výsledek po 4. průchodu: [1, 2, 4, 5, 8]

Další materiály:

• https://www.tutorialspoint.com/data_structures_algorithms/bubble_sort_algorithm.htm?authuser=1 

• https://algoritmy.net/article/3/Bubble-sort?authuser=1 

Povinný úkol

Implementace bubble sort.