Valiksortimine

Valikuga sortimine on sortimisalgoritm, täpsemalt on tegu võrdlussortimisega. Selle efektiivsusfaktor on sõltumata sisendandmete järjestusest formula_1, 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. 
Algoritm.
Algoritmi tööpõhimõte:
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:
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 formula_2 elementi (selleks kulub formula_3 võrdlust) ja siis leitud element vahetada esimesel positsioonil asuva elemendiga. Järgmise elemendi leidmiseks tuleb läbi uurida järgijäänud formula_3 elementi ja nõnda edasi, mis teeb kokku formula_5 võrdlust (vaata aritmeetiline jada). Pärast iga sortimata elementide läbimist toimub vahetus, mis teeb kokku formula_3 vahetust (kuna viimane element on juba paigas).
Võrdlus teiste sortimisalgoritmidega.
Lihtsate, keskmisel juhul formula_1 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 formula_8 elemendi õigele kohale paigutamiseks, kuid valikuga sortimine peab formula_8-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 formula_10 vahetust, samas kui vahelepanekuga sortimine sooritab formula_1 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 &lt; size; i++) {
 int min = i;
 int j;
 for (j = i + 1; j &lt; size; j++) {
 if (array[j] &lt; 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] &lt; A[s]:
 s = j
 A[i], A[s] = A[s], A[i]