Čo je výberové triedenie?
SELECTION SORT je porovnávací algoritmus triedenia, ktorý sa používa na triedenie náhodného zoznamu položiek vo vzostupnom poradí. Porovnanie nevyžaduje veľa priestoru navyše. Vyžaduje iba jeden ďalší pamäťový priestor pre časovú premennú.
Toto sa nazýva triedenie na mieste . Triedenie výberu má časovú zložitosť O (n 2 ), kde n je celkový počet položiek v zozname. Časová zložitosť meria počet iterácií potrebných na zoradenie zoznamu. Zoznam je rozdelený na dve oddiely: Prvý zoznam obsahuje zoradené položky, zatiaľ čo druhý zoznam obsahuje netriedené položky.
Triedený zoznam je predvolene prázdny a netriedený zoznam obsahuje všetky prvky. V netriedenom zozname sa potom vyhľadá minimálna hodnota, ktorá sa potom umiestni do zoradeného zoznamu. Tento proces sa opakuje, kým sa všetky hodnoty neporovnajú a nezoradia.
V tomto výučbe algoritmu sa dozviete:
- Čo je výberové triedenie?
- Ako funguje výberové triedenie?
- Definícia problému
- Riešenie (Algoritmus)
- Vizuálne znázornenie
- Program triedenia výberu pomocou Pythonu 3
- Vysvetlenie kódu
- Časová zložitosť výberu Zoradiť
- Kedy použiť výberové triedenie?
- Výhody výberu Zoradiť
- Nevýhody výberu Zoradiť
Ako funguje výberové triedenie?
Prvá položka v netriedenom oddiele sa porovnáva so všetkými hodnotami na pravej strane, aby sa skontrolovalo, či ide o minimálnu hodnotu. Ak to nie je minimálna hodnota, potom sa jej pozícia zamení s minimálnou hodnotou.
Príklad:
- Napríklad ak je index minimálnej hodnoty 3, potom sa hodnota prvku s indexom 3 umiestni do indexu 0, zatiaľ čo hodnota, ktorá bola v indexe 0, sa umiestni do indexu 3. Ak je prvý prvok v netriedenom oddiele minimálna hodnota, potom vráti svoje pozície.
- Prvok, ktorý bol určený ako minimálna hodnota, sa potom presunie do oddielu na ľavej strane, čo je zoradený zoznam.
- Rozdelená strana má teraz jeden prvok, zatiaľ čo nerozdelená strana má (n - 1) prvkov, kde n je celkový počet prvkov v zozname. Tento proces sa opakuje stále dokola, kým sa všetky položky neporovnajú a nezoradia na základe ich hodnôt.
Definícia problému
Zoznam prvkov, ktoré sú v náhodnom poradí, je potrebné zoradiť vzostupne. Nasledujúci zoznam považujte za príklad.
[21,6,9,33,3]
Vyššie uvedený zoznam by mal byť zoradený, aby sa dosiahli nasledujúce výsledky
[3,6,9,21,33]
Riešenie (Algoritmus)
Krok 1) Získajte hodnotu n, čo je celková veľkosť poľa
Krok 2) Rozdeľte zoznam na triedené a netriedené časti. Zoradená časť je spočiatku prázdna, zatiaľ čo netriedená časť obsahuje celý zoznam
Krok 3) Vyberte minimálnu hodnotu z nerozdelenej časti a vložte ju do triedenej časti.
Krok 4) Opakujte postup (n - 1) krát, kým nebudú zoradené všetky prvky v zozname.
Vizuálne znázornenie
Nasledujúci obrázok poskytuje zoznam piatich prvkov a ilustruje, ako algoritmus triedenia výberu iteruje cez hodnoty pri ich triedení.
Nasledujúci obrázok zobrazuje netriedený zoznam
Krok 1)
Prvá hodnota 21 sa porovnáva so zvyšnými hodnotami, aby sa skontrolovalo, či ide o minimálnu hodnotu.
3 je minimálna hodnota, takže polohy 21 a 3 sú zamenené. Hodnoty so zeleným pozadím predstavujú zoradený oddiel zoznamu.
Krok 2)
Hodnota 6, ktorá je prvým prvkom v netriedenom oddiele, sa porovnáva so zvyšnými hodnotami, aby sa zistilo, či existuje nižšia hodnota
Hodnota 6 je minimálna hodnota, takže si udržiava svoju pozíciu.
Krok 3)
Prvý prvok netriedeného zoznamu s hodnotou 9 sa porovnáva so zvyšnými hodnotami, aby sa skontrolovalo, či ide o minimálnu hodnotu.
Hodnota 9 je minimálna hodnota, takže si udržiava svoju pozíciu v triedenom oddiele.
Krok 4)
Hodnota 33 sa porovnáva so zvyšnými hodnotami.
Hodnota 21 je nižšia ako 33, takže polohy sa zamenia, aby sa vytvoril vyššie uvedený nový zoznam.
Krok 5)
V nerozdelenom zozname nám zostala iba jedna hodnota. Preto je už triedený.
Konečný zoznam je rovnaký ako zoznam uvedený na obrázku vyššie.
Program triedenia výberu pomocou Pythonu 3
Nasledujúci kód ukazuje implementáciu triedenia výberu pomocou Pythonu 3
def selectionSort( itemsList ):n = len( itemsList )for i in range( n - 1 ):minValueIndex = ifor j in range( i + 1, n ):if itemsList[j] < itemsList[minValueIndex] :minValueIndex = jif minValueIndex != i :temp = itemsList[i]itemsList[i] = itemsList[minValueIndex]itemsList[minValueIndex] = tempreturn itemsListel = [21,6,9,33,3]print(selectionSort(el))
Spustením vyššie uvedeného kódu získate nasledujúce výsledky
[3, 6, 9, 21, 33]
Vysvetlenie kódu
Vysvetlenie kódu je nasledujúce
Tu je vysvetlenie kódu:
- Definuje funkciu s názvom selectionSort
- Získava celkový počet prvkov v zozname. Potrebujeme to, aby sme určili počet prechodov, ktoré sa majú vykonať pri porovnávaní hodnôt.
- Vonkajšia slučka. Použije slučku na iteráciu cez hodnoty v zozname. Počet iterácií je (n - 1). Hodnota n je 5, takže (5 - 1) nám dáva 4. To znamená, že vonkajšie iterácie sa vykonajú 4 krát. V každej iterácii je hodnota premennej i priradená premennej minValueIndex
- Vnútorná slučka. Použije slučku na porovnanie hodnoty úplne vľavo s ostatnými hodnotami na pravej strane. Hodnota j však nezačína na indexe 0. Začína sa na (i + 1). To vylučuje hodnoty, ktoré už boli zoradené, takže sa zameriavame na položky, ktoré ešte neboli zoradené.
- Nájde minimálnu hodnotu v netriedenom zozname a umiestni ju na správne miesto
- Aktualizuje hodnotu minValueIndex, keď je podmienka zámeny pravdivá
- Porovnáva hodnoty indexových čísel minValueIndex a i a zisťuje, či nie sú rovnaké
- Hodnota úplne vľavo je uložená v časovej premennej
- Nižšia hodnota z pravej strany sa umiestni na prvú pozíciu
- Hodnota, ktorá bola uložená v časovej hodnote, je uložená na pozícii, ktorá bola predtým držaná minimálnou hodnotou
- Vráti zoradený zoznam ako výsledok funkcie
- Vytvorí zoznam el, ktorý má náhodné čísla
- Vytlačiť zoradený zoznam po vyvolaní výberu, ktorá ako parameter odovzdá funkciu triedenia.
Časová zložitosť výberu Zoradiť
Zložitosť zoradenia sa používa na vyjadrenie počtu časov vykonania potrebných na zoradenie zoznamu. Implementácia má dve slučky.
Vonkajšia slučka, ktorá vyberá hodnoty jednu po druhej zo zoznamu, sa vykoná n-krát, kde n je celkový počet hodnôt v zozname.
Vnútorná slučka, ktorá porovnáva hodnotu z vonkajšej slučky so zvyšnými hodnotami, sa tiež vykoná n-krát, kde n je celkový počet prvkov v zozname.
Preto je počet popráv (n * n), ktorý možno tiež vyjadriť ako O (n 2 ).
Výber má tri kategórie zložitosti;
- Najhorší prípad - tu je uvedený zoznam zostupne. Algoritmus vykonáva maximálny počet vykonaní, ktorý je vyjadrený ako [Big-O] O (n 2 )
- Najlepší prípad - nastane, keď je poskytnutý zoznam už zoradený. Algoritmus vykonáva minimálny počet vykonaní, ktorý je vyjadrený ako [Big-Omega] Ω (n 2 )
- Priemerný prípad - k tomu dôjde, keď je zoznam v náhodnom poradí. Priemerná zložitosť je vyjadrená ako [Big-theta] ⊝ (n 2 )
Výberové triedenie má priestorovú zložitosť O (1), pretože vyžaduje jednu časovú premennú použitú na zámenu hodnôt.
Kedy použiť výberové triedenie?
Triedenie výberu sa najlepšie používa, keď chcete:
- Malý zoznam položiek musíte zoradiť vzostupne
- Keď sú náklady na výmenu hodnôt zanedbateľné
- Používa sa tiež vtedy, keď sa potrebujete ubezpečiť, že boli skontrolované všetky hodnoty v zozname.
Výhody výberu Zoradiť
Nasledujú výhody druhu výberu
- Na malých zoznamoch si vedie veľmi dobre
- Je to algoritmus na mieste. Na triedenie nevyžaduje veľa miesta. Na uchovanie časovej premennej je potrebný iba jeden ďalší priestor.
- Má dobrý výkon pri položkách, ktoré už boli roztriedené.
Nevýhody výberu Zoradiť
Nasledujú nevýhody zoradenia podľa výberu.
- Pri práci na obrovských zoznamoch si vedie zle.
- Počet iterácií vykonaných počas triedenia je štvorcový, kde n je celkový počet prvkov v zozname.
- Ostatné algoritmy, napríklad quicksort, majú lepšiu výkonnosť v porovnaní s výberom.
Zhrnutie:
- Výberové triedenie je algoritmus porovnávania na mieste, ktorý sa používa na triedenie náhodného zoznamu do usporiadaného zoznamu. Má časovú zložitosť O (n 2 )
- Zoznam je rozdelený na dve časti, zoradené a netriedené. Minimálna hodnota sa vyberie z netriedenej časti a umiestni sa do triedenej časti.
- Táto vec sa opakuje, kým nie sú zoradené všetky položky.
- Implementácia pseudokódu v Pythone 3 zahŕňa použitie dvoch cyklov for a príkazov if na kontrolu nevyhnutnosti výmeny
- Časová zložitosť meria počet krokov potrebných na zoradenie zoznamu.
- Najhoršia časová zložitosť nastane, keď je zoznam zostupne. Má časovú zložitosť [Big-O] O (n 2 )
- Najlepšia časová zložitosť nastane, keď je zoznam už vzostupne. Má časovú zložitosť [Big-Omega] Ω (n 2 )
- Priemerná časová zložitosť nastane, keď je zoznam v náhodnom poradí. Má časovú zložitosť [Big-theta] ⊝ (n 2 )
- Zoradenie podľa výberu je najlepšie použiť, ak máte malý zoznam položiek na zoradenie, nezáleží na výmene hodnôt a kontrola všetkých hodnôt je povinná.
- Triedenie výberu nefunguje dobre na veľkých zoznamoch
- Ostatné algoritmy triedenia, napríklad quicksort, majú lepší výkon v porovnaní s výberom.