Řazení hodnot v poli - Bubble Sort
Bublinkové řazení - řazení záměnou
Jedná se o jednoduchý algoritmus, vhodný pro malé počty hodnot. Je založen na porovnávání sousedících hodnot. Jeho efektivita je dána počtem procházení celé posloupnosti hodnot. Při každém průchodu „probublá“ maximální hodnota na konec posloupnosti.
Předpokládáme, že hodnoty jsou uloženy v poli a známe aktuální počet prvků v poli. V uvedených algoritmech řadíme hodnoty vzestupně.
Poznámky pro návrh funkce: vstupem do funkce budou určitě hodnoty uložené v poli a aktuální počet hodnot v poli. Funkce při seřazení změní uspořádání hodnot v poli, ale nic víc se funkcí nemění. Protože pole je vstupně-výstupním parametrem funkce, bude mít naše funkce jen 2 parametry (pole, počet). Funce je bez návratové hodnoty, bude tedy typu void.
První varianta:
Procházíme postupně hodnoty v poli a porovnáváme vždy dvě sousedící hodnoty. Když je první z nich větší než druhá (při vzestupném řazení), hodnoty zaměníme. Zároveň nastavíme, zda byla provedena záměna. Opakujeme, dokud byla při posledním průchodu provedena alespoň jedna záměna.
V případě, že hodnoty jsou od začátku seřazené, stačí jeden průchod. Algoritmus zjistí, že nebyla provedena záměna a končí.
void seradit( float cisla[], int pocet)
{
float pom;
int i, zamena;
do
{
zamena=0; //nastaveni promenne pro sledovani zameny
//zamena neni, na zacatku kazdeho pruchodu polem
//prochazeni pole do predposledniho prvku
for ( i = 0; i < pocet-1 ; i++)
{
if ( cisla[i] > cisla[i+1] )
{ //zamena sousedicich hodnot
pom = cisla[i];
cisla[i] = cisla[i+1];
cisla[i+1] = pom;
zamena=1; //nastaveni promenne pro sledovani zameny
//zamena nastala
}
}
}while(zamena == 1);
}
Zkuste upravit algoritmus pro sestupné řazení.
Druhá varianta:
Procházíme postupně posloupnost hodnot a porovnáváme vždy dvě sousedící hodnoty. Když je první z nich větší než druhá, hodnoty zaměníme. Pole hodnot neprocházíme vždy celé, ale posouváme postupně jeho konec. Souvisí to s tím, že na konec se při každém průchodu dostane aktuální maximum.
void seradit( float cisla[], int pocet)
{
float pom;
int i, j;
for (j = pocet - 1; j >= 0; j-- )
{
for ( i = 0; i < j ; i++)
{
if ( cisla[i] > cisla[i+1] )
{ //zamena sousedicich hodnot
pom = cisla[i];
cisla[i] = cisla[i+1];
cisla[i+1] = pom;
}
}
}
}
Uvedený postup není příliš efektivní v případě, že máme již seřazené hodnoty.
Existují i další varianty algoritmu Bubble sort, je možné např. spojit výhody obou uvedených variant.