Kako se koristi sortiranje odabira

Selekcijsko sortiranje je tehnika sortiranja koja odabire stavku popisa, a zatim zamijeni svoje mjesto s drugom. Odabire najveću stavku, a zatim je zamjenjuje stavkom s najvišim indeksom popisa.

Algoritam to radi više puta dok se popis ne sortira. Ako niste sasvim sigurni kako sortiranje odabira funkcionira, došli ste na pravo mjesto. U nastavku ćemo to detaljnije objasniti, zajedno s prikazom primjera.

Sortiranje odabira: Bliži izgled

Pretpostavimo da imate popis: [39, 82, 2, 51, 30, 42, 7]. Da biste sortirali popis pomoću selekcijskog sortiranja, prvo biste trebali pronaći najveći broj u njemu.

Uz navedeni popis, taj je broj 82. Zamijenite 82 brojem s najvišim indeksom (odnosno 7).

Nakon prvog prolaska, novi redoslijed popisa bit će: [39, 7, 2, 51, 30, 42, 82]. Svaki put kad algoritam prođe kroz cijeli popis, to se naziva "prolaz".

Primijetite da popis tijekom postupka sortiranja održava razvrstani i nerazvrstani popis.

Povezano: Što je oznaka Big-O?

Izvorni popis započinje razvrstanim popisom nula stavki i nerazvrstanim popisom svih stavki. Zatim nakon prvog prolaska ima razvrstani popis koji ima samo broj 82.

Pri drugom prolazu, najveći broj na nesortiranom popisu bit će 51. Ovaj će se broj zamijeniti s 42 kako bi se dobio novi redoslijed popisa u nastavku:

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

Postupak se ponavlja dok se ne sortira cijeli popis. Slika u nastavku sažima cijeli postupak:

Brojevi podebljani crnom bojom pokazuju najveću vrijednost popisa u to vrijeme. Oni u zelenom prikazuju sortirani podlist.

Analiza algoritma

Da biste saznali složenost (pomoću Big-O notacije) ovog algoritma, slijedite dolje:

Na prvom prolazu se rade (n-1) usporedbe. Na drugom dodavanju, (n-2). Na trećem prolazu, (n-3) i tako dalje do (n-1) th prolaza, što čini samo jednu usporedbu.

Sažimajući usporedbe kako slijedi, daju se:

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

Stoga je sortiranje odabira O (n²).

Implementacija koda

Kôd prikazuje funkcije koje možete koristiti za izvršavanje sortiranja odabira pomoću Pythona i Jave.

Piton:

def selectionSort (moj popis):
za x u rasponu (len (mylist) - 1, 0, -1):
max_idx = 0
za posn u rasponu (1, x + 1):
ako je moj popis [posn]> moj popis [max_idx]:
max_idx = posn
temp = moj popis [x]
moj popis [x] = moj popis [max_idx]
moj popis [max_idx] = temp

Java:

void selectionSort (int my_array []) { 
za (int x = 0; x { 
indeks int = x; 
za (int y = x + 1; y if (my_array [y] indeks = y; // pronađi najniži indeks 
} 
} 
int temp = moj_ niz [indeks]; // temp je privremena pohrana
moj_ niz [indeks] = moj_ niz [x]; 
my_array [x] = temp; 
}}

Prelazak iz sortiranja odabira u sortiranje spajanja

Kao što je pokazala gornja analiza algoritma, algoritam sortiranja odabira je O (n²). Ima eksponencijalnu složenost i stoga je neučinkovit za vrlo velike skupove podataka.

Puno bolji algoritam za upotrebu bilo bi spajanje sortiranja složenosti O (nlogn). I sada znate kako funkcionira sortiranje odabira, sljedeće na popisu studija za algoritme sortiranja treba biti sortiranje spajanja.

O autoru