Valiksortimine

Allikas: Vikipeedia
Jump to navigation Jump to search

Valikuga sortimine on sortimisalgoritm, täpsemalt on tegu võrdlussortimisega. Selle efektiivsusfaktor on sõltumata sisendandmete järjestusest , 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[muuda | muuda lähteteksti]

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[muuda | muuda lähteteksti]

Teiste sortimisalgoritmidega võrreldes pole valikuga sortimist raske analüüsida, kuna selle tõhuses ei sõltu sorditavatest andmetest. Esimese elemendi leidmiseks tuleb vaadata läbi kõik elementi (selleks kulub võrdlust) ja siis leitud element vahetada esimesel positsioonil asuva elemendiga. Järgmise elemendi leidmiseks tuleb läbi uurida järgijäänud elementi ja nõnda edasi, mis teeb kokku võrdlust (vaata aritmeetiline jada). Pärast iga sortimata elementide läbimist toimub vahetus, mis teeb kokku vahetust (kuna viimane element on juba paigas).

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

Lihtsate, keskmisel juhul 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 elemendi õigele kohale paigutamiseks, kuid valikuga sortimine peab -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 vahetust, samas kui vahelepanekuga sortimine sooritab 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[muuda | muuda lähteteksti]

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[muuda | muuda 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 | muuda lähteteksti]