Jednorozměrné pole - konzole

Algoritmů řazení prvků vektoru existuje celá řada (cca přes 10 + modifikace). Nejjednodušší známý algoritmus je bublinkové řazení (anglicky "Bubble Sort"). Algoritmus funguje na principu průchodů. V každém průchodu je prozkoumán celý vektor od začátku do konce. Vždy jsou porovnávány dva prvky. U vzestupného řazení prvků vektoru je testována podmínka, když je první z prvků větší než druhý, dojde k prohození prvků. Po každém průchodu se dostaneme do určité fáze seřazení. Vektor je seřazen, když v posledním průchodu nedošlo k žádnému prohození - viz Obrázek 1. 

Obrázek 1: Bublinkové řazení prvků jednorozměrného pole

Před popisem vývojového diagramu algoritmu bublinkového řazení je třeba ukázat, jak prohodit dva prvky. Prohození dvou prvků nemůže být prováděno přímo. Ukažme si příklad, kdy potřebujeme prohodit v pořadí druhý prvek (index 1) se třetím prvkem vektoru (index 2) - viz Obrázek 2. 

Obrázek 2: Prohození dvou prvků vektoru

Pokud bychom přímo napsali příkaz pole[1] = pole[2], znamená to, že bychom do prvku s indexem 1 (v pořadí druhého prvku) přiřadili obsah prvku s indexem 2 (v pořadí třetího prvku). Tím by se obsah prvku s indexem 1 úplně ztratil, tj. hodnota 4  se přepíše na hodnotu 3 a budeme mít dvě hodnoty 3. Je zapotřebí deklarovat si pomocnou proměnnou, kam jedno z čísel "schováme", vybereme např. prvek s indexem 1 a přiřadíme ho do pomocné proměnné - viz Obrázek 3.

Obrázek 3: Prohození dvou prvků - pomocná proměnná - kopírování hodnoty do pomocné proměnné

Pak již můžeme číslo 4 v prvku s indexem 1 "zapomenout". Proto do prvku s indexem 1 uložíme hodnotu 3 z prvku s indexem 2 - viz Obrázek 4.

Obrázek 4: Prohození dvou prvků - kopírování hodnoty mezi prvky 

Do prvku s indexem 2 již můžeme uložit číslo 4, které je nyní uloženo v pomocné proměnné - viz Obrázek 5. Tím došlo k úspěšnému prohození obou prvků.

Obrázek 5: Prohození dvou prvků - kopírování hodnoty z pomocné proměnné do prvku 

Podívejme se nyní na vývojový diagram procedury SeraditPole - viz Obrázek 6. Procedura přijímá dva parametry - v prvním parametru je uložena velikost vektoru, druhý obsahuje samotný vektor, který má být setříděn vzestupně. Procedura obsahuje následující lokální proměnné:

• pom - pomocná proměnná pro dočasné uložení prvku
• i - index (pozice) prvku vektoru
• b - logická proměnná obsahující informaci, zda došlo k prohození některých sousedních prvků (tj. zda je již vektor seřazen - pokud b == false)

Uvnitř procedury jsou umístěny dva cykly. Vnější cyklus s podmínkou na konci se stará o kontrolu, zda je již vektor kompletně seřazen. Před proběhnutím vnitřního vnořeného cyklus s krokem, pomocí kterého procházíme jednotlivé prvky a porovnáváme vždy dva prvky z řady, je zapotřebí provést nastavení proměnné b na hodnotu false, tj. b = false. Tím je řečeno, že ještě před proběhnutím porovnání dvojic prvků neproběhlo žádné prohození dvou sousedních prvků.

Uvnitř těla cyklu s krokem je potřeba vždy porovnávat dva prvky. U řídící proměnné cyklu je tedy potřeba se zastavit (jako horní mez intervalu hodnot indexu i) na předposledním prvku, kdy porovnáme předposlední a poslední prvek (pokud bychom nechali řídící proměnnou cyklu nastavit na velikost vektoru, porovnávali bychom uvnitř těla cyklu poslední prvek s dalším prvkem, který však neexistuje). Pokud je při vzestupném řazení aktuálně procházený prvek větší než následující prvek (s indexem o 1 větší), je zapotřebí tyto prvky prohodit na základě principu, který jsme již probírali v předchozím textu. V opačném případě není zapotřebí prvky prohazovat. Pokud došlo alespoň k jednomu vzájemnému prohození prvků, je do proměnné b přiřazena hodnota true a díky tomu bude ve vnějším cyklu provedena další iterace. V případě, že úvodní předpoklad (b == true) stále platí i na konci průchodu prvky, dojde k ukončení algoritmu.

Obrázek 6: Podprogram SeraditPole - procedura pro seřazení prvků pole vzestupně podle jejich hodnoty