Veronika Dropčová
veronika.dropcova(at)gmail.com

   nika.blog.matfyz.sk

06 – Bubble sort

Dva algoritmy, s ktorými sa na výške jednoznačne stretnete. A s tým druhým možno aj neskôr v praxi.

 

Algoritmus triedenia (teda usporiadania prvkov podľa „veľkosti“) je v programátorskej praxi často vyhľadávaným algoritmom. A ako to už býva, neexistuje iba jedno správne (alebo použiteľné) riešenie.

 

Známe sú algoritmy s názvami ako bubble sortinsert sortselection sortmerge sort, random sort, či quick sort (a možno aj iné). Skúsme sa pozrieť na jeden z nich – pomalý, ale stabilný.

 

Bubble sort

Tak predstavme si, že máme na začiatku takéto 6-prvkové neusporiadané pole, ktorého prvky chceme usporiadať od najmenšieho po najväčší:

3 2 5 7 4 2

Bubble sort bude týmto poľom prechádzať niekoľkokrát a zakaždým bude porovnávať susediace dvojice. V prípade, že nájde „vľavo“ väčšie číslo ako „vpravo“, vymení ich. A bude pokračovať ďalšou dvojicou. Tak teda prvé prechádzanie poľom bude vyzerať takto:

1. krok: porovnávame 1. a 2. prvok
3 2 5 7 4 2 //2 je menej ako 3, vymení ich

2. krok: porovnávame 2. a 3. prvok
2 3 5 7 4 2 //3 nie je menej ako 5, nič sa nedeje

3. krok: porovnávame 3. a 4. prvok
2 3 5 7 4 2 //5 nie je menej ako 7, nič sa nedeje

4. krok: porovnávame 4. a 5. prvok
2 3 5 7 4 2 //4 je menej ako 7, vymení ich

5. krok: porovnávame 5. a 6. prvok
2 3 5 4 7 2 //2 je menej ako 7, vymení ich

//na konci prvého prechádzania poľom teda máme takéto pole: 
2 3 5 4 2 7

 

Keďže sme šli zľava doprava a vždy sme doprava posúvali väčšie číslo, máme istotu, že najväčšie číslo zo zadaného poľa je úplne vpravo, preto ho pri ďalších prechodoch nemusíme kontrolovať. Prichádza druhé prechádzanie:

1. krok: porovnávame 1. a 2. prvok
2 3 5 4 2 7 //3 nie je menej ako 2, nič sa nedeje

2. krok: porovnávame 2. a 3. prvok
2 3 5 4 2 7//5 nie je menej ako 3, nič sa nedeje

3. krok: porovnávame 3. a 4. prvok
2 3 5 4 2 7//4 je menej ako 5, vymení ich

4. krok: porovnávame 4. a 5. prvok
2 3 4 5 2 7//2 je menej ako 5, vymení ich

//ďalej už neporovnávame, lebo je tam už len číslo 7 a o tom už s istotou vieme, 
že je na správnom mieste, preto na konci druhého prechádzania poľom teda máme takéto pole: 
2 3 4 2 5 7

A pokračujeme ďalej tretím prechádzaním poľom, pričom už nás nebudú zaujímať posledné dva prvky, tie už majú isto dobré miesto:

1. krok: porovnávame 1. a 2. prvok
2 3 4 2 5 7 //3 nie je menej ako 2, nič sa nedeje

2. krok: porovnávame 2. a 3. prvok
2 3 4 2 5 7//4 nie je menej ako 3, nič sa nedeje

3. krok: porovnávame 3. a 4. prvok
2 3 4 2 5 7//2 je menej ako 4, vymení ich

//ďalej už neporovnávame, na konci tretieho prechádzania poľom teda máme takéto pole: 
2 3 2 4 5 7


A prichádza štvrté prechádzanie poľom, pričom už nekontrolujeme tri prvky od konca:

1. krok: porovnávame 1. a 2. prvok
2 3 2 4 5 7 //3 nie je menej ako 2, nič sa nedeje

2. krok: porovnávame 2. a 3. prvok
2 3 2 4 5 7//2 je menej ako 3, vymení ich


//ďalej už neporovnávame, štvrtého prechádzania poľom teda máme takéto pole: 
2 2 3 4 5 7

Posledné prechádzanie poľom (teda piate) pred nami:

1. krok: porovnávame 1. a 2. prvok
2 3 2 4 5 7 //3 nie je menej ako 2, nič sa nedeje


//ďalej už neporovnávame, na konci piateho prechádzania poľom teda máme takéto pole: 
2 2 3 4 5 7

Všimnite si, koľkokrát sme museli prechádzať poľom (5x). A to je všetko. Pole je utriedené.