Valintalajittelun käyttäminen

Valintalajittelu on lajittelutekniikka, joka valitsee luettelokohteen ja vaihtaa sen jälkeen paikan toisen kanssa. Se valitsee suurimman kohteen ja vaihtaa sen sitten luettelon korkeimmassa hakemistossa olevan kohteen kanssa.

Algoritmi tekee tämän toistuvasti, kunnes luettelo on lajiteltu. Jos et ole aivan varma, kuinka valintalajittelu toimii, olet tullut oikeaan paikkaan. Selitämme sen tarkemmin jäljempänä yhdessä esimerkin kanssa.

Valintalajittelu: Tarkempi ilme

Oletetaan, että sinulla on luettelo: [39, 82, 2, 51, 30, 42, 7]. Jos haluat lajitella luettelon valintalajittelun avulla, sinun on ensin löydettävä siitä suurin numero.

Annetulla luettelolla tämä luku on 82. Vaihda 82 korkeimman indeksin numerolla (eli 7).

Ensimmäisen kierroksen jälkeen uusi luettelojärjestys on: [39, 7, 2, 51, 30, 42, 82]. Joka kerta, kun algoritmi käy läpi koko luettelon, sitä kutsutaan "läpäisyksi".

Huomaa, että luettelossa on lajiteltu alilista ja lajittelematon aliluettelo lajitteluprosessin aikana.

Liittyvät: Mikä on Big-O-merkintä?

Alkuperäinen luettelo alkaa lajiteltu luettelo nollasta ja lajittelematon luettelo kaikista kohteista. Ensimmäisen kierroksen jälkeen sillä on lajiteltu luettelo, jolla on vain numero 82.

Toisella kierroksella lajittelemattoman alaluettelon suurin luku on 51. Tämä numero vaihdetaan 42: een, jotta saadaan uusi alla oleva luettelojärjestys:

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

Prosessi toistetaan, kunnes koko luettelo on lajiteltu. Alla olevassa kuvassa on yhteenveto koko prosessista:

Lihavoidut mustat numerot osoittavat korkeinta luetteloarvoa tuolloin. Vihreät osoittavat lajiteltu alaluettelo.

Algoritmianalyysi

Saadaksesi tämän algoritmin monimutkaisuuden (käyttäen Big-O-notaatiota), seuraa alla olevia ohjeita:

Ensimmäisellä kierroksella tehdään (n-1) vertailuja. Toisella kierroksella (n-2). Kolmannella kierroksella (n-3) ja niin edelleen, kunnes (n-1). Kulku tekee vain yhden vertailun.

Yhteenveto alla olevista vertailuista antaa:

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

Siksi valintalaji on O (n²).

Koodin toteutus

Koodi näyttää toiminnot, joita voit käyttää valintalajittelun suorittamiseen Pythonilla ja Javalla.

Python:

def selectionSort (mylist):
x: lle alueella (len (mylist) - 1, 0, -1):
max_idx = 0
posnille alueella (1, x + 1):
if mylist [posn]> mylist [max_idx]:
max_idx = posn
temp = omat listani [x]
omat listani [x] = omat listani [max_idx]
oma luettelo [max_idx] = lämpötila

Java:

void selectionSort (int my_array []) { 
for (int x = 0; x { 
int-indeksi = x; 
for (int y = x + 1; y jos (my_array [y] indeksi = y; // etsi alin indeksi 
} 
} 
int temp = my_array [hakemisto]; // temp on väliaikainen tallennustila
my_array [index] = my_array [x]; 
my_array [x] = lämpötila; 
}}

Siirtyminen valintalajittelusta lajitteluun yhdistämiseen

Kuten edellä esitetty algoritmianalyysi on osoittanut, valintalajittelualgoritmi on O (n²). Sillä on eksponentiaalinen monimutkaisuus ja se on siksi tehoton erittäin suurille tietojoukoille.

Paljon parempi käytettävä algoritmi olisi yhdistämislajittelu O: n (nlogn) monimutkaisuuteen. Ja nyt tiedät, miten valintalajittelu toimii, seuraavaksi tutkimusluettelossasi lajittelualgoritmien tulisi olla yhdistämislajittelu.

Kirjailijasta