Třídění výběru: Algoritmus vysvětlený pomocí Python Příklad kódu

Co je výběrové řazení?

VÝBĚR TŘÍDĚNÍ je srovnávací třídicí algoritmus, který se používá k třídění náhodného seznamu položek ve vzestupném pořadí. Porovnání nevyžaduje mnoho místa navíc. Vyžaduje pouze jeden paměťový prostor navíc pro dočasnou proměnnou.

Toto je známé jako na místě třídění. Třídění výběru má časovou složitost O(n²) kde n je celkový počet položek v seznamu. Časová složitost měří počet iterací potřebných k seřazení seznamu. Seznam je rozdělen do dvou oddílů: První seznam obsahuje seřazené položky, zatímco druhý seznam obsahuje neseřazené položky.

Ve výchozím nastavení je seřazený seznam prázdný a neseřazený seznam obsahuje všechny prvky. Netříděný seznam je poté prohledán na minimální hodnotu, která je pak umístěna do setříděného seznamu. Tento proces se opakuje, dokud nejsou všechny hodnoty porovnány a seřazeny.

Jak funguje výběrové řazení?

První položka v netříděném oddílu se porovná se všemi hodnotami na pravé straně, aby se zjistilo, zda se jedná o minimální hodnotu. Pokud to není minimální hodnota, pak je její pozice prohozena s minimální hodnotou.

Příklad

Pokud je například index minimální hodnoty 3, pak je hodnota prvku s indexem 3 umístěna na index 0, zatímco hodnota, která byla na indexu 0, je umístěna na index 3. Pokud je první prvek v netříděném oddílu minimální hodnotu, pak vrátí své pozice.
Prvek, který byl určen jako minimální hodnota, se poté přesune do oddílu na levé straně, což je seřazený seznam.
Rozdělená strana má nyní jeden prvek, zatímco nerozdělená strana má (n – 1) prvků, kde n je celkový počet prvků v seznamu. Tento proces se opakuje stále dokola, dokud nejsou všechny položky porovnány a seřazeny podle jejich hodnot.

Definice problému

Seznam prvků, které jsou v náhodném pořadí, je třeba seřadit vzestupně. Zvažte následující seznam jako příklad.

[21,6,9,33,3]

Výše uvedený seznam by měl být seřazen tak, aby poskytl následující výsledky

[3,6,9,21,33]

Řešení (algoritmus)

Krok 1) Získejte hodnotu n, což je celková velikost pole

Krok 2) Rozdělte seznam na seřazené a neseřazené části. Seřazená sekce je zpočátku prázdná, zatímco neseřazená sekce obsahuje celý seznam

Krok 3) Vyberte minimální hodnotu z nerozdělené sekce a umístěte ji do setříděné sekce.

Krok 4) Tento proces (n – 1) opakujte, dokud nebudou seřazeny všechny prvky v seznamu.

Vizuální reprezentace

Vzhledem k tomu, že je uveden seznam pěti prvků, následující obrázky ilustrují, jak algoritmus třídění výběru iteruje hodnoty při jejich řazení.

Následující obrázek ukazuje neseřazený seznam

Krok 1)

První hodnota 21 se porovná se zbytkem hodnot, aby se zjistilo, zda se jedná o minimální hodnotu.

3 je minimální hodnota, takže pozice 21 a 3 jsou prohozeny. Hodnoty se zeleným pozadím představují seřazený oddíl seznamu.

Krok 2)

Hodnota 6, která je prvním prvkem v neseřazeném oddílu, se porovná se zbytkem hodnot, aby se zjistilo, zda existuje nižší hodnota.

Hodnota 6 je minimální hodnota, udržuje si tedy svou pozici.

Krok 3)

První prvek netříděného seznamu s hodnotou 9 je porovnán se zbytkem hodnot, aby se zjistilo, zda se jedná o minimální hodnotu.

Hodnota 9 je minimální hodnota, takže si zachovává svou pozici v seřazeném oddílu.

Krok 4)

Hodnota 33 je porovnána se zbytkem hodnot.

Hodnota 21 je nižší než 33, takže pozice jsou prohozeny, aby vznikl výše uvedený nový seznam.

Krok 5)

V nerozděleném seznamu nám zbývá pouze jedna hodnota. Proto je již vytříděný.

Konečný seznam je jako na obrázku výše.

Výběr Třídění programu pomocí Python 3

Následující kód ukazuje implementaci řazení výběru pomocí Python 3

def selectionSort( itemsList ):
    n = len( itemsList )
    for i in range( n - 1 ): 
        minValueIndex = i

        for j in range( i + 1, n ):
            if itemsList[j] < itemsList[minValueIndex] :
                minValueIndex = j

        if minValueIndex != i :
            temp = itemsList[i]
            itemsList[i] = itemsList[minValueIndex]
            itemsList[minValueIndex] = temp

    return itemsList


el = [21,6,9,33,3]

print(selectionSort(el))

Spuštěním výše uvedeného kódu získáte následující výsledky

[3, 6, 9, 21, 33]

Vysvětlení kódu

Vysvětlení kódu je následující

Zde je vysvětlení kódu:

Definuje funkci s názvem selectionSort
Získá celkový počet prvků v seznamu. Potřebujeme to k určení počtu průchodů, které je třeba provést při porovnávání hodnot.
Vnější smyčka. Používá smyčku k iteraci přes hodnoty seznamu. Počet iterací je (n – 1). Hodnota n je 5, takže (5 – 1) nám dává 4. To znamená, že vnější iterace budou provedeny 4krát. V každé iteraci je hodnota proměnné i přiřazena proměnné minValueIndex
Vnitřní smyčka. Používá smyčku k porovnání hodnoty nejvíce vlevo s ostatními hodnotami na pravé straně. Hodnota pro j však nezačíná na indexu 0. Začíná na (i + 1). Tím se vyloučí hodnoty, které již byly seřazeny, takže se zaměříme na položky, které ještě nebyly seřazeny.
Vyhledá minimální hodnotu v neseřazeném seznamu a umístí ji na správné místo
Aktualizuje hodnotu minValueIndex, když je podmínka výměny pravdivá
Porovná hodnoty indexových čísel minValueIndex a i, aby zjistil, zda nejsou stejné
Hodnota nejvíce vlevo je uložena v časové proměnné
Spodní hodnota z pravé strany zaujímá pozici první
Hodnota, která byla uložena v časové hodnotě, je uložena na pozici, která byla dříve držena minimální hodnotou
Vrátí seřazený seznam jako výsledek funkce
Vytvoří seznam, který obsahuje náhodná čísla
Vytiskněte seřazený seznam po zavolání funkce Seřadit předáním el jako parametru.

Časová složitost třídění výběru

Složitost řazení se používá k vyjádření počtu spuštění, které je potřeba k seřazení seznamu. Implementace má dvě smyčky.

Vnější smyčka, která vybírá hodnoty jednu po druhé ze seznamu, se provede nkrát, kde n je celkový počet hodnot v seznamu.

Vnitřní smyčka, která porovnává hodnotu z vnější smyčky se zbytkem hodnot, se také provede nkrát, kde n je celkový počet prvků v seznamu.

Počet provedení je tedy (n * n), což lze také vyjádřit jako O(n²).

Druh výběru má tři kategorie složitosti, a to;

Nejhorší případ – zde je uvedený seznam v sestupném pořadí. Algoritmus provede maximální počet provedení, který je vyjádřen jako [Big-O] O(n²)
Nejlepší případ – k tomu dojde, když je poskytnutý seznam již seřazen. Algoritmus provede minimální počet provedení, který je vyjádřen jako [Big-Omega] ?(n²)
Průměrný případ – k tomu dochází, když je seznam v náhodném pořadí. Průměrná složitost je vyjádřena jako [Big-theta] a(n²)

Řazení výběru má prostorovou složitost O(1), protože vyžaduje jednu časovou proměnnou používanou pro výměnu hodnot.

Kdy použít výběrové řazení?

Třídění výběru se nejlépe používá, když chcete:

Musíte seřadit malý seznam položek ve vzestupném pořadí
Když jsou náklady na swapování hodnot nevýznamné
Používá se také, když se potřebujete ujistit, že byly zkontrolovány všechny hodnoty v seznamu.

Výhody třídění výběru

Níže jsou uvedeny výhody selekčního druhu

Funguje velmi dobře na malých seznamech
Je to algoritmus na místě. Nevyžaduje mnoho místa na třídění. Pro uložení časové proměnné je potřeba pouze jedno místo navíc.
Funguje dobře u položek, které již byly roztříděny.

Nevýhody třídění výběru

Následují nevýhody selekce.

Při práci na velkých seznamech funguje špatně.
Počet iterací provedených během třídění je n-kvadratický, kde n je celkový počet prvků v seznamu.
Jiné algoritmy, jako je quicksort, mají lepší výkon ve srovnání s výběrem.

Shrnutí

Třídění výběru je místní porovnávací algoritmus, který se používá k řazení náhodného seznamu do uspořádaného seznamu. Má časovou složitost O(n²)
Seznam je rozdělen na dvě části, seřazené a netříděné. Minimální hodnota je vybrána z netříděné sekce a umístěna do seřazené sekce.
Toto se opakuje, dokud nejsou všechny položky seřazeny.
Implementace pseudokódu v Python 3 zahrnuje použití dvou for cyklů a příkazů if ke kontrole, zda je výměna nezbytná
Časová složitost měří počet kroků potřebných k seřazení seznamu.
Nejhorší případ časové složitosti nastane, když je seznam v sestupném pořadí. Má časovou složitost [Big-O] O(n²)
Časová složitost v nejlepším případě nastane, když je seznam již ve vzestupném pořadí. Má časovou složitost [Big-Omega] ?(n²)
K časové složitosti průměrného případu dochází, když je seznam v náhodném pořadí. Má časovou složitost [Big-theta] ?(n²)
Výběrové třídění se nejlépe používá, když máte malý seznam položek k třídění, na ceně výměny hodnot nezáleží a kontrola všech hodnot je povinná.
Řazení výběru nefunguje dobře na velkých seznamech
Jiné třídicí algoritmy, jako je rychlé třídění, mají lepší výkon ve srovnání s třídicím výběrem.

Máš rád: