Kuidas kasutada valiku sortimist

Valikusortimine on sorteerimistehnika, mis valib loendiüksuse ja vahetab seejärel koha teisega. See valib suurima üksuse ja vahetab selle seejärel loendi kõrgeima indeksi üksusega.

Algoritm teeb seda korduvalt, kuni loend on sorditud. Kui te pole päris kindel, kuidas valiku sortimine töötab, olete jõudnud õigesse kohta. Selgitame seda põhjalikumalt koos näite näitamisega.

Valiku sortimine: lähem pilk

Oletame, et teil on nimekiri: [39, 82, 2, 51, 30, 42, 7]. Valiku sortimise abil loendi sortimiseks peaksite kõigepealt leidma selles suurima numbri.

Antud loendis on see arv 82. Vaheta 82 kõrgeima indeksi (st 7) ​​numbriga.

Pärast esimest läbimist on uus nimekirja järjekord: [39, 7, 2, 51, 30, 42, 82]. Iga kord, kui algoritm läbib kogu loendi, nimetatakse seda läbipääsuks.

Pange tähele, et loend säilitab sortimisprotsessi ajal sorditud alamloendi ja sortimata alamloendi.

Seotud: Mis on Big-O tähistamine?

Algne loend algab nullist üksuste järjestatud loendiga ja kõigi üksuste sortimata loendiga. Siis on pärast esimest läbimist sorditud loend, millel on ainult number 82.

Teisel läbimisel saab sorteerimata alamloendis kõige rohkem numbreid 51. See number vahetatakse 42-ga, et anda järgmine nimekirja järjekord:

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

Protsessi korratakse seni, kuni kogu loend on sorditud. Alloleval joonisel on kogu protsess kokku võetud:

Paksus mustas kirjas olevad numbrid näitavad sel ajal suurimat loendi väärtust. Rohelistel on sorditud alamloend.

Algoritmi analüüs

Selle algoritmi keerukuse (kasutades Big-O tähistust) saamiseks järgige allpool toodud juhiseid.

Esimesel läbimisel tehakse (n-1) võrdlused. Teisel läbimisel (n-2). Kolmandal läbimisel (n-3) ja nii edasi kuni (n-1) kolmanda läbini, mis teeb ainult ühe võrdluse.

Allpool toodud võrdluste kokkuvõte annab:

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

Seetõttu on valiku sort O (n²).

Koodi rakendamine

Kood näitab funktsioone, mida saate kasutada Pythoni ja Java abil valiku sorteerimiseks.

Python:

def selectionSort (minu nimekiri):
x-i jaoks vahemikus (len (minu nimekiri) - 1, 0, -1):
max_idx = 0
posn jaoks vahemikus (1, x + 1):
if mylist [posn]> mylist [max_idx]:
max_idx = posn
temp = minu nimekiri [x]
minu nimekiri [x] = loend [max_idx]
minu nimekiri [max_idx] = temp

Java:

void selectionSort (int my_array []) { 
jaoks (int x = 0; x { 
int indeks = x; 
jaoks (int y = x + 1; y kui (my_array [y] indeks = y; // leida madalaim indeks 
} 
} 
int temp = my_array [indeks]; // temp on ajutine salvestusruum
my_array [register] = my_array [x]; 
my_array [x] = temp; 
}}

Edasi liikumine valiku sortimiselt sortimise ühendamiseni

Nagu ülaltoodud algoritmianalüüs on näidanud, on valiku sorteerimise algoritm O (n²). See on eksponentsiaalse keerukusega ja seetõttu väga suurte andmekogumite jaoks ebaefektiivne.

Palju parem algoritm, mida kasutada, oleks liita sortimine O (nlogn) keerukusega. Ja nüüd teate, kuidas valiku sortimine töötab, algoritmide sorteerimiseks peaksite oma õppeloendis järgmisena olema ühendamise sort.

Autori kohta