Ako používať výberové triedenie

Zoradenie podľa výberu je technika triedenia, pri ktorej sa vyberie položka zoznamu a potom sa zamení miesto za inú. Vyberie najväčšiu položku a potom ju zamení za položku v najvyššom indexe zoznamu.

Algoritmus to robí opakovane, kým nie je zoznam zoradený. Ak si nie ste celkom istí, ako funguje triedenie výberu, ste na správnom mieste. Ďalej to vysvetlíme podrobnejšie spolu s ukážkou príkladu.

Zoradenie výberu: Bližší pohľad

Predpokladajme, že máte zoznam: [39, 82, 2, 51, 30, 42, 7]. Ak chcete zoznam zoradiť pomocou zoradenia podľa výberu, musíte v ňom najskôr nájsť najvyššie číslo.

Pri danom zozname je to číslo 82. Zamieňajte 82 s číslom v najvyššom indexe (tj. 7).

Po prvom prechode bude nové poradie zoznamu: [39, 7, 2, 51, 30, 42, 82]. Zakaždým, keď algoritmus prejde celým zoznamom, nazýva sa to „vyhovujúci“.

Všimnite si, že v zozname sa počas procesu triedenia udržuje zoradený podradený zoznam a netriedený podradený zoznam.

Súvisiace: Čo je to Big-O notácia?

Pôvodný zoznam začína zoradeným zoznamom nulových položiek a netriedeným zoznamom všetkých položiek. Potom po prvom prejdení má zoradený zoznam, ktorý má iba číslo 82.

Pri druhom prechode bude najvyšší počet v netriedenom podnázve 51. Toto číslo bude vymenené za 42, aby sa získalo nové poradie zoznamu nižšie:

[39, 7, 2, 42, 30, 51, 82].

Proces sa opakuje, kým nie je zoradený celý zoznam. Na nasledujúcom obrázku je zhrnutý celý proces:

Čísla tučným čiernym písmom ukazujú najvyššiu hodnotu zoznamu v danom čase. Zelené zobrazujú triedený podzoznam.

Analýza algoritmov

Ak chcete získať zložitosť (pomocou notácie Big-O) tohto algoritmu, postupujte nasledovne:

Pri prvom prechode sa uskutočnia (n-1) porovnania. Pri druhom prechode (n-2). Pri treťom prechode (n-3) a tak ďalej až po (n-1) th prechod, ktorý robí iba jedno porovnanie.

Zhrnutie porovnaní uvedených nižšie dáva:

(n-1) + (n-1) + (n-1) +... + 1 = ((n-1) n) / 2.

Preto je výberový výber O (n²).

Implementácia kódu

Tento kód zobrazuje funkcie, ktoré môžete použiť na vykonávanie triedenia výberu pomocou jazykov Python a Java.

Python:

def selectionSort (môj zoznam):
pre x v rozsahu (len (môj zoznam) - 1, 0, -1):
max_idx = 0
pre pozíciu v rozsahu (1, x + 1):
ak mylist [posn]> mylist [max_idx]:
max_idx = posn
temp = mylist [x]
mylist [x] = mylist [max_idx]
mylist [max_idx] = tepl

Java:

void selectionSort (int my_array []) { 
pre (int x = 0; x { 
int index = x; 
pre (int y = x + 1; y if (my_array [y] index = y; // nájsť najnižší index 
} 
} 
int temp = my_array [index]; // temp je dočasné úložisko
my_array [index] = my_array [x]; 
my_array [x] = teplota; 
}}

Pokračovanie od výberu zoradenia k zlúčeniu zoradenia

Ako ukázala vyššie uvedená algoritmická analýza, algoritmus výberu je O (n²). Má exponenciálnu zložitosť, a preto je neúčinný pre veľmi veľké súbory údajov.

Oveľa lepším algoritmom na použitie by bolo zlúčenie druhu so zložitosťou O (nlogn). A teraz viete, ako funguje výberové triedenie. Ďalším bodom v zozname štúdií pre algoritmy triedenia by malo byť zlučovanie.

O autorovi