Valikuga sortimine

Allikas: Vikipeedia

Sorteerimine

Valikuga sortimine
Vahelepanemisega sortimine
Mullisortimine

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

  1. Leia miinimumväärtus loetelust
  2. Vaheta see väätusega esimesel positsioonil
  3. 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