Jak používat řazení výběru

Třídění výběru je technika řazení, která vybere položku seznamu a poté zamění její místo s jinou. Vybírá největší položku a poté ji vymění za položku v nejvyšším indexu seznamu.

Algoritmus to dělá opakovaně, dokud není seznam seřazen. Pokud si nejste zcela jisti, jak funguje třídění výběru, jste na správném místě. Níže to vysvětlíme podrobněji a ukážeme vám příklad.

Třídění výběru: Bližší pohled

Předpokládejme, že máte seznam: [39, 82, 2, 51, 30, 42, 7]. Chcete-li seřadit seznam pomocí řazení výběru, musíte v něm nejprve najít nejvyšší číslo.

S daným seznamem je to číslo 82. Zaměňte 82 s číslem v nejvyšším indexu (tj. 7).

Po prvním průchodu bude nové pořadí seznamu: [39, 7, 2, 51, 30, 42, 82]. Pokaždé, když algoritmus projde celým seznamem, nazývá se to „průchod“.

Všimněte si, že seznam během procesu třídění udržuje seřazený sublist a netříděný sublist.

Příbuzný: Co je Big-O notace?

Původní seznam začíná seřazeným seznamem nulových položek a netříděným seznamem všech položek. Poté po prvním průchodu má seřazený seznam, který má pouze číslo 82.

Při druhém průchodu bude nejvyšší počet v netříděném podřízeném seznamu 51. Toto číslo bude vyměněno za 42 za účelem zadání nového pořadí seznamu níže:

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

Proces se opakuje, dokud není seřazen celý seznam. Níže uvedený obrázek shrnuje celý proces:

Čísla tučně černě ukazují nejvyšší hodnotu seznamu v té době. Ti v zelené barvě ukazují seřazený podlist.

Analýza algoritmů

Chcete-li získat složitost (pomocí notace Big-O) tohoto algoritmu, postupujte níže:

Při prvním průchodu se provede (n-1) srovnání. Při druhém průchodu (n-2). Při třetím průchodu (n-3) atd. Až do (n-1) tého průchodu, který provede pouze jedno srovnání.

Shrnutí srovnání, jak je uvedeno níže, dává:

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

Proto je výběr řazení O (n²).

Implementace kódu

Tento kód zobrazuje funkce, které můžete použít k provedení výběru pomocí Pythonu a Javy.

Krajta:

def selectionSort (můj seznam):
pro x v rozsahu (len (mylist) - 1, 0, -1):
max_idx = 0
pro posn v rozsahu (1, x + 1):
pokud můj seznam [posn]> můj seznam [max_idx]:
max_idx = posn
temp = můj seznam [x]
mylist [x] = mylist [max_idx]
mylist [max_idx] = tepl

Jáva:

void selectionSort (int my_array []) { 
pro (int x = 0; x { 
int index = x; 
pro (int y = x + 1; y if (my_array [y] index = y; // najít nejnižší index 
} 
} 
int temp = my_array [index]; // temp je dočasné úložiště
my_array [index] = my_array [x]; 
my_array [x] = teplota; 
}}

Přechod od výběru řazení k sloučení řazení

Jak ukázala výše uvedená analýza algoritmu, je algoritmus výběru řazení O (n²). Má exponenciální složitost, a proto je neúčinný pro velmi velké datové sady.

Mnohem lepším algoritmem by bylo sloučení typu se složitostí O (nlogn). A teď víte, jak funguje třídění výběru, další ve vašem studijním seznamu pro třídicí algoritmy by mělo být sloučení.

O autorovi