Kā izmantot atlases kārtošanu

Atlases kārtošana ir šķirošanas tehnika, kas atlasa saraksta vienumu un pēc tam maina vietu ar citu. Tas atlasa lielāko vienumu un pēc tam to maina ar vienumu saraksta augstākajā indeksā.

Algoritms to dara atkārtoti, līdz saraksts ir sakārtots. Ja neesat īsti pārliecināts, kā darbojas atlases kārtošana, esat nonācis īstajā vietā. Tālāk mēs to paskaidrosim dziļāk, kā arī parādīsim piemēru.

Atlases kārtošana: tuvāks izskats

Pieņemsim, ka jums ir saraksts: [39, 82, 2, 51, 30, 42, 7]. Lai kārtotu sarakstu, izmantojot atlases kārtošanu, vispirms tajā jāatrod lielākais skaitlis.

Dotajā sarakstā šis skaitlis ir 82. Apmainiet 82 ar skaitli augstākajā indeksā (tas ir, 7).

Pēc pirmās iziešanas jaunā saraksta kārtība būs: [39, 7, 2, 51, 30, 42, 82]. Katru reizi, kad algoritms iziet visu sarakstu, to sauc par “caurlaidi”.

Ievērojiet, ka kārtošanas procesā saraksts saglabā sakārtotu apakšsarakstu un nesakārtotu apakškārtu.

Saistīts: Kas ir Big-O apzīmējums?

Sākotnējais saraksts sākas ar sakārtotu nulles vienumu sarakstu un visu preču nesakārtotu sarakstu. Tad pēc pirmās caurlaides tam ir sakārtots saraksts, kuram ir tikai skaitlis 82.

Pie otrās piespēles lielākais skaits nešķirotajā apakškārtā būs 51. Šis numurs tiks apmainīts ar 42, lai izveidotu jauno saraksta secību zemāk:

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

Process tiek atkārtots, līdz viss saraksts ir sakārtots. Zemāk redzamais attēls apkopo visu procesu:

Treknrakstā melnā krāsā norādītie skaitļi tajā laikā norāda augstāko saraksta vērtību. Tie, kas ir zaļā krāsā, parāda sakārtoto apakškopu.

Algoritmu analīze

Lai iegūtu šī algoritma sarežģītību (izmantojot Big-O apzīmējumu), veiciet tālāk norādītās darbības.

Pirmajā piegājienā tiek veikti (n-1) salīdzinājumi. Otrajā piespēlē (n-2). Trešajā reizē (n-3) un tā tālāk līdz (n-1) trešajai kārtai, kas salīdzina tikai vienu.

Apkopojot zemāk sniegtos salīdzinājumus, iegūstam:

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

Tāpēc atlases šķirošana ir O (n²).

Kodu ieviešana

Kods parāda funkcijas, kuras varat izmantot atlases kārtošanas veikšanai, izmantojot Python un Java.

Python:

def selectionSort (savs saraksts):
x diapazonā (len (mans saraksts) - 1, 0, -1):
max_idx = 0
pozn diapazonā (1, x + 1):
ja mans saraksts [posn]> mans saraksts [max_idx]:
max_idx = pozn
temp = mans saraksts [x]
mans saraksts [x] = mans saraksts [max_idx]
savs saraksts [max_idx] = temp

Java:

void selectionSort (int my_array []) { 
par (int x = 0; x { 
int indekss = x; 
par (int y = x + 1; y ja (my_array [y] indekss = y; // atrast zemāko indeksu 
} 
} 
int temp = my_array [indekss]; // temp ir pagaidu krātuve
my_array [index] = my_array [x]; 
my_array [x] = temp; 
}}

Pāriet no atlases kārtošanas uz apvienošanu

Kā parādīja iepriekšminētā algoritma analīze, atlases šķirošanas algoritms ir O (n²). Tam ir eksponenciāla sarežģītība, un tāpēc tas ir neefektīvs ļoti lielām datu kopām.

Daudz labāks algoritms, ko izmantot, būtu apvienot šķirošanu ar O (nlogn) sarežģītību. Un tagad jūs zināt, kā darbojas atlases kārtošana. Nākamajā savā algoritmu šķirošanas pētījumu sarakstā jābūt apvienošanas kārtībai.

Par autoru