Řadící algoritmy #1

Jedná se o takový algoritmus, který je schopný ze vstupního souboru dat vytvořit jejich posloupnost v předem určených podmínkách. Každý algoritmus se snaží najít takovou posloupnost, pro kterou platí, že předchozí prvek je menší nebo roven a následující prvek je větší nebo roven k aktuálnímu prvku, dle kritérií, které řazení určují.

Pro řazení existuje spousta hotových algoritmů, které se liší v mnoha aspektech, jako je složitost, stabilita, nebo metoda pro řazení.

Od těchto vlastností se odvíjí také požadavky, které jsou na algoritmy kladeny:

Minimální paměťové požadavky (paměťová složitost)
Rychlost (časová složitost)
Délka a srozumitelnost kódu
Stabilita
Přirozenost

Paměťová náročnost
je mnohdy podceňovaným faktorem a je pravda, že v některých případech není až tak důležitá (od toho se odvíjí výběr správného altoritmu), ale ve většině případů je právě tento požadavek velmi
sorting
důležitý, hlavně při řazení velkého počtu záznamů.

Rychlost altoritmu, nebo její časová složitost, je ovlivňována počtem operací, které je nutno se vstupním souborem provést a je ovlivněna i počtem prvků, které jsou ve vstupním souboru dat. Většinou je tato složitost kvadratická, logaritmická nebo lineární, dle výběru algoritmu.

Délka kódu není až tak důležitý faktor, ale v praxi většinou platí, že čím kratší kód, tím efektivnější zpracování vstupu. Ovšem není to podmínkou.

Stabilita určuje, zda budou seřazené prvky souhlasit s jejích klíči. Většinou jsou při řazení využívány klíče a hodnoty, které se řadí závisle nebo nezávisle na sobě.

Přirozenost je vlastnost, kdy algoritmus je přirozený v případě, že čas řazení již z části seřazené vstupní posloupnosti je menší než čas pro řazení neseřazené posloupnosti.

Podle využívání paměti jsou algoritmy ještě členěny na vnitřní a vnější. Při použití vnitřního algoritmu je nutné, aby byla všechna data načtena a uložena v operační paměti, kam k nim algoritmus přistupuje
Vnější algoritmy se využijí zejména při řazení velkého množství dat, kdy není možné všechna data mít načtená a načítá se jenom část dat, které se postupně řadí.

Bubble sort (bublinkové řazení)

Bubble sort je jeden ze základních algoritmů řazení. Princip spočívá v porovnávání vždy dvou prvků, kdy vstupní soubor dat procházíme od počátku ke konci a dle podmínek řazení vždy tyto dva prvky prohazujeme nebo necháváme netknuté.

Nevýhoda spočívá v tom, že abychom dostali seřazenou posloupnost, je nutné celý vstupní soubor dat projít tolikrát, kolik obsahuje hodnot, od čehož se odvíjí právě velká časová náročnost tohoto algoritmu.

Název Bublinkové řazení (Bubble sort) vznikl právě z principu algoritmu, kdy největší prvky v souboru dat postupně při každém dalším procházení probublávají směrem doprava (dle použitého algoritmu).

Ukázka jednoduchého Bubble sortu v Javě, pro seřazení pole celých čísel, může vypadat takto:

//pomocna promenna
int tmp;
//v cyklku projdeme cele pole 
 for (int i = 0; i &lt; InArray.length - 1; i++) {
     for (int j = 0; j &lt; InArray.length - i - 1; j++){
         //porovname dve sousedni hodnoty
         if (InArray[j + 1] &lt; InArray[j]) {
             /*
             V pripade, ze nasledujici hodota 
             je mensi nez predchozi, tyto dve hodnoty prohodime
              */
             //do pomocne promenne ulozime puvodni hodnotu
             tmp = InArray[j];
             //druhou hodnotu posuneme na prvni pozici
             InArray[j] = InArray[j + 1];
             //na druhou hodnotu ulozime puvodn prvni hodnotu
             InArray[j + 1] = tmp;
         }
       }
    }
    //vracime jiz serazene pole

    return InArray;

}

//pomocna promenna

int tmp;

//v cyklku projdeme cele pole

for (int i = 0; i < InArray.length - 1; i++) {

for (int j = 0; j < InArray.length - i - 1; j++){

//porovname dve sousedni hodnoty

if (InArray[j + 1] < InArray[j]) {

V pripade, ze nasledujici hodota

je mensi nez predchozi, tyto dve hodnoty prohodime

//do pomocne promenne ulozime puvodni hodnotu

tmp = InArray[j];

//druhou hodnotu posuneme na prvni pozici

InArray[j] = InArray[j + 1];

//na druhou hodnotu ulozime puvodn prvni hodnotu

InArray[j + 1] = tmp;

}

//vracime jiz serazene pole

return InArray;

}

I když je po principiální stránce algoritmus dost pomalý, jde na internetu najít spoustu různých upravených alternativ, které jej vylepšují.

Existuje ještě jedno využití tohoto algoritmu, které je na rozdíl od řazení jedno z nejrychlejších. Jedná se o případ, kdy chceme zjistit, zda je vstupní soubor dat již seřazený nebo nikoli. Pro toto zjištění nám stačí jenom jeden průchod všech vstupních hodnot, při kterém porovnáváme vždy hodnoty dvou, vedle sebe, ležících prvků.

Ukázka takové funkce může v Javě vypadat takto:

public boolean IsSorted_BubbleSort( int[] InArray){
    // v jednom cyklu projdeme celé pole
    for( int i = 0; i &lt; InArray.length - 1; i++ ){
        //pokud je následující prvek menší než předchozí,
        //vracíme false
        if( InArray[ i ] &gt; InArray[ i+1 ] )
            return false;
    }
    //vracíme true
    return true;
}

public boolean IsSorted_BubbleSort( int[] InArray){

// v jednom cyklu projdeme celé pole

for( int i = 0; i < InArray.length - 1; i++ ){

//pokud je následující prvek menší než předchozí,

//vracíme false

if( InArray[ i ] > InArray[ i+1 ] )

return false;

}

//vracíme true

return true;

}

Přirozený: Ano
Stabilní: Ano
Minimální časová složitost: O(n)
Průměrná časová složitost: O(n^2)
Maximální časová složitost: O(n^2)

Insertion sort (řazení vkládáním)

Insertion sort je další z algoritmů, který je založen na porovnávání hodnot, podobně jako Bubble sort, ovšem princip je zcela odlišný.

Algoritmus pracuje tak, že prochází neseřazenou strukturu, a každý aktuálně zpracovávaný prvek přesune na jeho konečné místo (některou z konců struktury), kam patří.

Jak vyplívá z podstaty, jeho časová složitost se přímo odvíjí od struktury vstupních dat. Pokud jsou data částečně seřazena, je algoritmus velmi rychlí. Stejně tak je velmi rychlí pro malé obsahy vstupních dat.

Od principu řazení se opět odvíjí název – řazení vkládáním (Insertion sorting), kdy se vstupní prvky struktury přímo vkládají na místo kam patří.

Další výhodou algoritmu je, že dokáže řadit „online“. To znamená, že umožňuje seřadit i předem nenačtenou strukturu, ale hodnoty můžeme do struktury postupně přidávat. Algoritmus nemusí předem znát celkový počet prvků. Takže umožňuje do seřazené struktury velmi jednoduše vložit další prvek a celou strukturu vrátit opět seřazenou.

Ukázkový kód v Javě, pro seřazení pole celých čísel, může vypadat takto:

public int[] InsertingSort(int[] InArray ) {
    //v cylku projdeme cele pole od druheho prvku
    //prvni prvek by nebylo kam presouvat
    for (int i = 1; i &lt; InArray.length; i++ ) {
        //ulozime si hodnoty aktualniho prvku
        int value = InArray[ i ];
        //ulozime si pozici predchoziho prvku
        int n = i - 1;
        //vsechny prvni posuneme o jednu pozici doprava
        //az do mista, na ktere patri nas prvek
        while( ( n &gt;= 0 ) &amp;&amp; ( value &lt; InArray[ n ] ) ){
            InArray[ n + 1 ] = InArray[ n ];
            --n;
        }
        //umistime nas aktualne zpracovavany prvek
        InArray[ n + 1 ] = value;
    }
    //vracime serazene pole
    return InArray;
}

public int[] InsertingSort(int[] InArray ) {

//v cylku projdeme cele pole od druheho prvku

//prvni prvek by nebylo kam presouvat

for (int i = 1; i < InArray.length; i++ ) {

//ulozime si hodnoty aktualniho prvku

int value = InArray[ i ];

//ulozime si pozici predchoziho prvku

int n = i - 1;

//vsechny prvni posuneme o jednu pozici doprava

//az do mista, na ktere patri nas prvek

while( ( n >= 0 ) && ( value < InArray[ n ] ) ){

InArray[ n + 1 ] = InArray[ n ];

--n;

}

//umistime nas aktualne zpracovavany prvek

InArray[ n + 1 ] = value;

}

//vracime serazene pole

return InArray;

}

Přirozený: Ano
Stabilní: Ano
Minimální časová složitost: O(n)
Průměrná časová složitost: O(n^2)
Maximální časová složitost: O(n^2)

Slection sort (řazení výběrem)

Selection sort je principiálně velmi jednoduchý algoritmus. Cílem je postupně procházet celou strukturu vstupních hodnot, ve kterých se hledá vždy nejmenší prvek (nebo největší prvek, dle užití algoritmu), který se posune na konec struktury (nebo na začátek). Tímto postupem se nám postupně zmenšuje počet hodnot, ve kterých je nutné vyhledávat, a na konci (nebo začátku) struktury nám vzniká již seřazená posloupnost.

Nevýhodou je, že i když je na vstupu již částečně seřazená struktura, algoritmus to nerozlišuje a jeho složitost a časová náročnost je pořád stejná, protože se postupně zpracovávají všechny prvky.
Název je opět odvozen od principu, protože algoritmus projde celé pole a vybere v něm jeden, vyhovující, prvek, který zařadí na jedenu z krajních pozic. Při každém průchodu se počet hodnot zmenšuje o jednu (n-1) a tento postup se opakuje, dokud nejsou všechny prvky vyčerpány (n = 0).

Opět jednoduchá ukázka v Javě, pro seřazení pole celých čísel, může vypadat takto:

public int[] SelectionSort(int[] InArray) {
    int key;
    // v cylku projdeme cele pole
    for (int i = 0; i &lt; InArray.length - 1; i++) {
        //hledame minimum v poli
        //nejmensi hodnotu si nastavime jako aktualni hodnotu
        key = i;
        //v cylku projdeme od dalsi hodnoty
        for( int j = i + 1; j &lt; InArray.length; j++ ){
            //porovnavame, zda je hodnota mensi nez naze aktualne ulozena hodnota v key
            if( InArray[ j ] &lt; InArray[ key ] )
                //pokud ano, nastavime ji jako aktualni
                key = j;
        }
        //zaradime hodnotu na spravne misto
        int tmp = InArray[ i ];
        InArray[ i ] = InArray[ key ];
        InArray[ key ] = tmp;
    }
    //vracime serazene pole
    return InArray;
}

public int[] SelectionSort(int[] InArray) {

int key;

// v cylku projdeme cele pole

for (int i = 0; i < InArray.length - 1; i++) {

//hledame minimum v poli

//nejmensi hodnotu si nastavime jako aktualni hodnotu

key = i;

//v cylku projdeme od dalsi hodnoty

for( int j = i + 1; j < InArray.length; j++ ){

//porovnavame, zda je hodnota mensi nez naze aktualne ulozena hodnota v key

if( InArray[ j ] < InArray[ key ] )

//pokud ano, nastavime ji jako aktualni

key = j;

}

//zaradime hodnotu na spravne misto

int tmp = InArray[ i ];

InArray[ i ] = InArray[ key ];

InArray[ key ] = tmp;

}

//vracime serazene pole

return InArray;

}

Přirozený: Ne
Stabilní: Ano
Časová složitost: O(n^2)

Závěrem

Toto jsou tři nejjednodušší řadící algoritmy, se kterými se můžete v praxi setkat. Jejich implementace nemusí být nutně taková, jak je zde uvedeno, a všechny tyto algoritmy je možné libovolně upravit a změnit tak některou jejich vlastnost, většinou na úkor vlastnosti jiné.
V příštím článku se podíváme na další, složitější, řadící algoritmy.

Comments are closed for this page

Honzajscz

27/10/2008

Článek jsem jen tak proletl, ale na konci mě zarazilo slovní spojení "v praxi setkáte". Ja nevím jak ty, ale já bych se ani s jedním z těchto algoritmů setkal nechtěl, protože by mě to mohlo stát dost času. Tyto algoritmy jsou více méně teoretická věc, která se nepoužívá. Něco jako dvoudobí spalovací motor v autech. Prostě překonáno. Jinak pěkný článek a jen tak dál vzhuru k NP

Tommy

27/10/2008

Zarazilo mě, že píšeš, že Select sort je stabilní, podle mě stabilní neni.

malejpavouk

27/10/2008

V praxi jde potkat insertion sort jakozto vypln quicsortu pro maly pole (i kdyz i tam byl placnul shell sort)…jinak souhlasim…tohle se v praxi moc nepotka, protoze A) jazyky maji implementovany n*log(n) algoritmy v knihovnach, B) tyhle algoritmy jsou dost pomaly

Ale spis bych se pozastavil nad

"Délka kódu není až tak důležitý faktor, ale v praxi většinou platí, že čím kratší kód, tím efektivnější zpracování vstupu. Ovšem není to podmínkou."

coz je docela nesmysl…takovej heapsort neni zrovna kratkej a je optimalni, takovej bubble sort je kratkej a optimalni neni, radix sort ma 3 radky a slozitost (k*n) 🙂

Tom

27/10/2008

Selection sort podle tohoto kódu je nestabilni

bautech Porcelanato liquido quanto custa

13/06/2017