Valiksortimine

Allikas: Vikipeedia

Valikuga sortimine on sortimisalgoritm, täpsemalt on tegu võrdlussortimisega. Selle efektiivsusfaktor on O(n^2), sõltumata sisendandmete järjestusest, olles nõnda ebaefektiivne suurte hulkade korral, ning üldjuhul annab halvemaid või sarnaseid tulemusi kui samalaadne vahelepanekuga sortimine. Valikuga sortimist loetakse üheks lihtsamaks sortimisalgoritmiks ning teatud olukordades võib see olla efektiivsem kui mõni keerulisem algoritm.

Valikuga sortimine – animatsioon

Algoritm[muuda | redigeeri lähteteksti]

Algoritm töötab nii:

  1. Otsi loendist väikseim element
  2. Vaheta see esimesel kohal oleva elemendiga
  3. Korda tegevust ülejäänud loendile (sorteerimata osa)

Loend jaotub kaheks osaks: juba sorteeritud elemendid, mis reastuvad vasakult paremale alates loendi esimesest elemendist, ning sorteerimata elemendid, mis hõlmavad ülejäänud rea.

Näide, kuidas valikuga sortimine sorteerib viis elementi:

64 25 12 22 11

11 25 12 22 64

11 12 25 22 64

11 12 22 25 64

11 12 22 25 64   

Viimase reaga ei toimunud mingit muutust, kuna viimased 2 elementi olid juba õiges järjestuses. Algoritm ei olnud siiski veel lõpule jõudnud ning seetõttu otsis sorteerimata osast veel kord minimaalse elemendi, mis aga oli juba oma õigel kohal.

Analüüs[muuda | redigeeri lähteteksti]

Teiste sortimisalgoritmidega võrreldes pole valikuga sortimist raske analüüsida, kuna selle 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 element vahetada 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) + \ldots + 2 + 1 = \frac{n(n-1)}{2} \in O(n^2) võrdlust (vaata aritmeetiline jada). Pärast iga sorteerimata elementide läbimist toimub vahetus, mis teeb kokku n - 1 vahetust (kuna viimane element on juba paigas).

Võrdlus teiste sortimisalgoritmidega[muuda | redigeeri lähteteksti]

Lihtsate, keskmisel juhul O(n^2) keerukusega algoritmide seas suudab valikuga sortimine peaaegu alati edestada mullsortimist, kuid on üldiselt nõrgem, kui vahelepanekuga sortimine. Vahelepanekuga sortimine on pärast k-ndat iteratsiooni sarnane valikuga sortimisele, kuna loendi k esimest elementi on sorteeritud. Vahelepanekuga sortimise eelis on, et see käib läbi ainult nii palju elemente, kui on vaja, et paigutada k + 1 element õigele kohale, kuid valikuga sortimine peab läbi käima kõik ülejäänud elemendid, et leida k + 1-ne element.

Analüüs näitab, et vahelepanekuga sortimine sooritab tavaliselt poole vähem võrdlusi kui valikuga sortimine, kuid võib teha sama palju või palju vähem, sõltuvalt algsest järjestusest. Mõne reaalaja-rakenduse jaoks võib olla eeliseks, et valikuga sortimine kulutab sortimiseks alati ühepalju aega, sõltumata algsest järjestusest. Sageli on see eeliseks vahelepanekuga sortimise ees, kuna see on palju efektiivsem, kui loend on juba sorteeritud või peaaegu sorteeritud.

Teine suur erinevus on, et valikuga sortimine sooritab alati O(n) vahetust, samas kui vahelepanekuga sortimine sooritab O(n^2) vahetust nii halvimal kui ka keskmisel juhul. Kuna vahetused nõuavad loendisse kirjutamist, siis valikuga sortimine on eelistatav, kui mällu kirjutamine on palju ressursinõudlikum kui lugemine. See on sageli nii, kui loend on lühike, aga elemendid on väga suured. Pole ühtegi vähem andmeid liigutavat sortimisalgoritmi.

Valikuga sortimine on suurte loendite korral oluliselt nõrgem jaga-ja-valitse tüüpi algoritmidest nagu kiirsortimine. Siiski on valikuga sortimine või vahelepanekuga sortimine tüüpiliselt kiiremad väikeste loendite korral (vähem kui 10–20 elementi). Kasulik optimeering rekursiivsete sortimisalgoritmide jaoks on kasutada valikuga sortimist või vahelepanekuga sortimist piisavalt väikeste alamloendite korral.

Implementatsioon[muuda | redigeeri lähteteksti]

C/C++ valikuga sortimise implementatsioon, kasutades viitmuutujaid:

void selectionSort( int* array, unsigned size ) {
    unsigned i;
    for (i = 0; i < size; ++i) {
        unsigned min = i;
        unsigned j;
        for (j = i + 1; j < size; ++j) {
            if (array[j] < array[min]) {
                min = j;
            }
        }
        if (min != i) {
            int swap = array[ i ];
            array[ i ] = array[ min ];
            array[ min ] = swap;
        }
    }
}

Implementatsioon Pythonis:

def selection_sort(A) :
    for j in range(0,len(A)-1) :
        s = j
        for i in range(j,len(A) ) :
            if ( A[i] < A[s] ) : s = i  
        A[j] , A[s] = A[s] , A[j]
    return A

Viited[muuda | redigeeri lähteteksti]

  • Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Leheküljed 138–141, paragrahv 5.2.3: Valikuga sorteerimine

Välislingid[muuda | redigeeri lähteteksti]