Valiksortimine

Valikuga sortimine on sortimisalgoritm, täpsemalt on tegu võrdlussortimisega. Selle efektiivsusfaktor on sõltumata sisendandmete järjestusest $O(n^{2})$, mis muudab algoritmi suurte hulkade korral vähetõhusaks 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 mõnest keerulisemast algoritmist tõhusam.

Valikuga sortimine – animatsioon

Algoritm

Algoritmi tööpõhimõte:

1. Otsitakse loendist väikseim element;
2. Vahetakse leitud element esimesel kohal oleva elemendiga;
3. Korratakse tegevust ülejäänud loendile (sortimata osale).

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

Näide viie elemendi sortimisest:

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 muutust ei toimunud, kuna kaks viimast elementi olid juba õiges järjestuses. Algoritm ei olnud siiski veel lõpule jõudnud ning seetõttu otsis sortimata osast veel kord väikseimat elementi, mis aga oli juba oma õigel kohal.

Analüüs

Teiste sortimisalgoritmidega võrreldes pole valikuga sortimist raske analüüsida, kuna selle tõhusus ei sõltu sorditavatest andmetest. Esimese elemendi leidmiseks tuleb vaadata läbi kõik $n$ elementi (selleks kulub $n-1$ võrdlust) ja siis leitud element vahetada esimesel positsioonil asuva elemendiga. Järgmise elemendi leidmiseks tuleb läbi uurida järgijää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 sortimata elementide läbimist toimub vahetus, mis teeb kokku $n-1$ vahetust (kuna viimane element on juba paigas).

Võrdlus teiste sortimisalgoritmidega

Lihtsate, keskmisel juhul $O(n^{2})$ keerukusega algoritmide seas suudab valikuga sortimine peaaegu alati edestada mullsortimist, kuid on üldiselt nõrgem vahelepanekuga sortimisest. 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 $k+1$ elemendi õigele kohale paigutamiseks, kuid valikuga sortimine peab $k+1$-ne elemendi leidmiseks käima läbi kõik ülejäänud elemendid.

Analüüsi järgi sooritab vahelepanekuga sortimine tavaliselt poole vähem võrdlusi kui valikuga sortimine, kuid võib sõltuvalt algsest järjestusest teha sama palju või palju vähem. Mõne reaalaja-rakenduse jaoks võib olla eeliseks, et sõltumata algsest järjestusest kulutab valikuga sortimine alati ühepalju aega. Sageli on see eeliseks vahelepanekuga sortimise ees, kuna juba sorditud või peaaegu sorditud loendi puhul on see on palju tõhusam.

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 juhul, kui mällu kirjutamine on palju ressursinõudlikum kui lugemine. See on sageli nii lühikese, kuid suurte elementidega loendi puhul. 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

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

void selectionSort(int* array, int size) {
    int i;
    for (i = 0; i < size; i++) {
        int min = i;
        int 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 i in range(0, len(A)-1):
        s = i
        for j in range(i, len(A)):
            if A[j] < A[s]:
                s = j
        A[i], A[s] = A[s], A[i]

Viited

• 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

• Animated Sorting Algorithms: Selection Sort – graafikaline demonstratsioon ja arutelu valikuga sortimisest