Valikuga sortimine
Allikas: Vikipeedia
Sorteerimine |
---|
Valikuga sortimine |
Valikuga sortimine on sortimisalgoritm, täpsemalt on tegu korduva minimaalse/maksimaalse elemendi sortimisega võrdluse teel. Ta omab Θ(n2) efektiivsusfaktorit, olles nõnda ebaefektiivne suurte hulkade korral, ning üldjuhul annab halvemaid või sarnaseid tulemusi kui samalaadne vahelepanemisega sortimine. Valikuga sortimist loetakse üheks lihtsaimaks sortimisalgoritmiks ning teatud olukordades võib ta olla efektiivsem kui mõni keerulisem algoritm.
[redigeeri] Tööpõhimõte
- Leia miinimumväärtus loetelust
- Vaheta see väätusega esimesel positsioonil
- Korda kahte esimest tegevust (võttes ületäitumisel järgmise elemendi)
Näide kuidas sortimise algoritm töötab viie elemendi korral:
31 25 12 22 11 //võrdlen 4 korda, vahetan 3 korda 11 25 12 22 31 //võrdlen 3 korda, vahetan 3 korda 11 12 25 22 31 //võrdlen 2 korda, vahetan 3 korda 11 12 22 25 31 //võrdlen 1 korra, vahetan 3 korda //Θ(n*2)
Näide teisele poole sortimisest:
31 25 12 22 11 //võrdlen 4 korda 31 25 12 22 11 //võrdlen 3 korda 31 25 22 12 11 //võrdlen 2 korda, vahetan 3 korda 31 25 22 12 11 //võrdlen 1 korra //Θ(n*2)
[redigeeri] Analüüs
Valikuga sortimist pole raske analüüsida, kuna tema efektiivsus ei sõltu sorditavatest andmetest. Esimese elemendi leidmiseks tuleb uurida läbi kõik n elementi (selleks kulub n - 1 võrdlust) ja siis leitud elemendi vahetamisega elemendiga, mis asub esimesel positsioonil. Järgmise elemendi leidmiseks tuleb läbi uurida järgi jäänud n - 1 elementi ja nõnda edasi, mis teeb kokku (n - 1) + (n - 2) + ... + 2 + 1 = Θ(n2) võrdlust. Iga võrdlemisprotseduuri lõpus toimub vahetamine, mis teeb kokku n - 1 vahetust (kuna viimane element on juba paigas).
[redigeeri] Rakendus
void selection(int *array, int length){ int max, i, temp; while(length > 0) { max = 0; for(i = 1; i < length; i++) if(array[i] > array[max]) max = i; temp = array[length-1]; array[length-1] = array[max]; array[max] = temp; length--; } }
[redigeeri] Vaata ka
- Sorteerimine