Valiksortimine: erinevus redaktsioonide vahel
Eemaldatud sisu Lisatud sisu
AvocatoBot (arutelu | kaastöö) P r2.7.1) (Robot: lisatud th:การเรียงลำดับแบบเลือก |
P masintoim using AWB |
||
31. rida:
Lihtsate, keskmisel juhul <math>O(n^2)</math> keerukusega algoritmide seas suudab valikuga sortimine peaaegu alati edestada [[mullsortimine|mullsortimist]], kuid on üldiselt nõrgem, kui [[vahelepanemisega sortimine|vahelepanekuga sortimine]]. Vahelepanekuga sortimine on pärast ''k''-ndat [[iteratsioon]]i 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 <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.
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-rakendus
Teine suur erinevus on, et valikuga sortimine sooritab alati <math>O(n)</math> vahetust, samas kui vahelepanekuga sortimine sooritab <math>O(n^2)</math> 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
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 [[rekursioon|rekursiivsete]] sortimisalgoritmide jaoks on kasutada valikuga sortimist või vahelepanekuga sortimist piisavalt väikeste alamloendite korral.
== Implementatsioon ==
[[
<source lang="c">
| |||