Valiksortimine: erinevus redaktsioonide vahel

'''Valikuga sortimine''' on [[sortimisalgoritm]], täpsemalt on tegu võrdlussortimisega. Ta omab ''<math>O(n<sup>^2)</supmath>)'' [[efektiivsusfaktor]]it, sõltumata sisendandmete järjestusest, olles nõnda ebaefektiivne suurte hulkade korral, ning üldjuhul annab halvemaid või sarnaseid tulemusi kui samalaadne [[vahelepanemisega sortimine|vahelepanekuga sortimine]]. Valikuga sortimist loetakse üheks lihtsaimaks sortimisalgoritmiks ning teatud olukordades võib ta olla efektiivsem kui mõni keerulisem algoritm.

Valikuga sortimist pole raske analüüsida võrreldes teiste sortimisalgoritmidega, kuna tema efektiivsus ei sõltu sorditavatest andmetest. Esimese elemendi leidmiseks tuleb uurida läbi kõik ''<math>n''</math> elementi (selleks kulub ''<math>n'' - 1</math> võrdlust) ja siis leitud element vahetada elemendiga, mis asub esimesel positsioonil. Järgmise elemendi leidmiseks tuleb läbi uurida järgi jäänud ''<math>n'' - 1</math> elementi ja nõnda edasi, mis teeb kokku <math>(n −- 1) + (n −- 2) + ...\ldots + 2 + 1 = \frac{n(n − -1) / }{2} ∈\in ''O(n<sup>^2) </supmath>)'' võrdlust (vaata [[aritmeetiline jada]]). Pärast iga sorteerimata elementide läbimist toimub vahetus, mis teeb kokku '' <math>n'' - 1</math> vahetust (kuna viimane element on juba paigas).

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

Teine suur erinevus on, et valikuga sortimine sooritab alati ''<math>O(n)''</math> vahetust, kui vahelepanekuga sortimine sooritab ''<math>O(n<sup>^2)</supmath>)'' 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 [[sortimisalgoritm|sortimisalgoritmi]]

Implementatsioon [[Python (programeerimiskeelprogrammeerimiskeel)|Python'is]]: