Vahelepanemisega sortimine: erinevus redaktsioonide vahel
Eemaldatud sisu Lisatud sisu
Matemaatika mõista Hulk on siinkohal vale asi, millele viidata |
ümberstruktureeritud |
||
1. rida:
'''Vahelepanemisega sortimine''' ([[inglise keel|inglise]] ''insertion sort'') on [[sortimisalgoritm]], täpsemalt on tegu võrdlussortimisega, mis ehitatakse ühe [[sisestus]]e haaval. Antud [[sortimine]] on mõeldud eeskätt viitavale [[loetelu]]le, kus elemendi lisamiseks tuleb vahetada väiksemalt elemendilt viit endale (ja/või temale) ja luua viit suuremale/võrdsele elemendile (ja/või temalt).
Vahelepanemisega sortimise keskmine [[Algoritmiline keerukus|keerukus]] on Θ(''n''<sup>2</sup>/4), mis tähendab, et see on ebaefektiivne suurte andmehulkade korral, kuid omab siiski mitmeid eeliseid:
* Lihtne programmeerida
* Efektiivne (üsna) väikeste andmehulkade puhul
* Efektiivne andmehulkade puhul mis on juba osaliselt sorditud
* Efektiivseim nn. lihtsatest Θ(''n''<sup>2</sup>) efektiivsusfaktorit omavatest algoritmidest
*
* igale-antud-kohale tüüpi algoritm, nõuab fikseeritud suurusega vahemäluala (puhvrit) O(1)
* ''Online''-tüüpi algoritm, sortida saab siis, kui andmeid saadakse
==
# Kustuta elemendi viidad
20. rida ⟶ 21. rida:
# Korda kahte viimast tegevust
===
<source lang="c">▼
void insertSort(int a[], size_t length) {▼
int i, j, value;▼
for(i = 1; i < length; i++) {▼
value = a[i];▼
for (j = i - 1; j >= 0 && a[j] > value; j--) {▼
a[j + 1] = a[j];▼
}▼
a[j + 1] = value;▼
}▼
}▼
</source>▼
=== Näited ===
Näide, kuidas sortimise algoritm töötab viie elemendi korral (-> sümboliseerib ühepoolset viitamist):
53. rida ⟶ 71. rida:
Üks universaalne sortimisprotseduur oleks sortida keeruka sortimisalgoritmiga algselt andmed ära ja lõpetada vahelepanemisega sortimisega.
▲<source lang="c">
▲void insertSort(int a[], size_t length) {
▲ int i, j, value;
▲ for(i = 1; i < length; i++) {
▲ value = a[i];
▲ for (j = i - 1; j >= 0 && a[j] > value; j--) {
▲ a[j + 1] = a[j];
▲ }
▲ a[j + 1] = value;
▲ }
▲}
▲</source>
| |||