Lomituslajittelu
![](http://upload.wikimedia.org/wikipedia/commons/c/cc/Merge-sort-example-300px.gif)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/6/60/Mergesort_algorithm_diagram.png/300px-Mergesort_algorithm_diagram.png)
Lomituslajittelu (limityslajittelu, lomitusjärjestäminen, Merge sort) on asymptoottiselta suoritusajaltaan tehokas (Θ( log )) ja vakaa lajittelumenetelmä, mutta vaatii tavallisella vektorimuotoisella taulukolla lisämuistia (O(n)). Erityisen hyödyllinen se on kuitenkin linkitettyjen listojen järjestämiseen, jolloin lisämuistia ei tarvita. Se toimii pääpiirteissään seuraavasti:
- Jaa taulukko kahteen yhtä suureen osataulukkoon
- Järjestä osataulukot rekursiivisesti
- Lomita järjestyksessä olevat osataulukot takaisin yhdeksi järjestyksessä olevaksi taulukoksi
Esimerkkitoteutus
Ohessa pseudokielinen toteutus 'tavalliselle' taulukolle:
algoritmi Lomituslajittelu(taulukko t, lisätaulukko l, kokonaisluku alku, kokonaisluku loppu) if alku >= loppu then // Korkeintaan 1 alkio, ei tarvitse järjestää lopeta algoritmin suoritus else if alku + 1 = loppu then // 2 alkiota, helppo järjestää if t[alku] < t[loppu] then Vaihda alkioiden t[alku] ja t[loppu] arvot keskenään end if else // Järjestetään puolikkaat rekursiivisesti ja lomitetaan väli := (alku + loppu)/2 // Katkaisukohta (pyöristetään alaspäin) Lomituslajittelu(t,l,alku,väli) // Järjestetään puolikkaat Lomituslajittelu(t,l,väli+1,loppu) // Lomitetaan lisätaulukkoon ja kopioidaan alkuperäiseen taulukkoon i := alku // 1. puolikkaan indeksi j := väli + 1 // 2. puolikkaan indeksi k := alku // Lomituksen indeksi while k ⇐ loppu // Käsitellään kaikki välin alkiot // Vertaillaan kummankin puolikkaan suurinta jäljellä olevaa arvoa // ja sijoitetaan suurempi lomitukseen seuraavaksi // Jos jommassakummassa puolikkaassa ei ole alkioita jäljellä, // siirretään kaikki toisen puolikkaan alkiot if i > väli then // 1. puolikkaassa ei alkioita while j ⇐ loppu l[k] := t[j] k := k + 1 j := j + 1 end while else if j > loppu // 2. puolikkaassa ei alkioita while i ⇐ väli l[k] := t[i] k := k + 1 i := i + 1 end while else // Molemmissa puolikkaissa alkioita if t[i] > t[j] then l[k] := t[i] i := i+1 else l[k] := t[j] j := j+1 end if k := k + 1 end if end while // Kopioidaan lomitus alkuperäiseen taulukkoon for a = alku to loppu t[a] = l[a] end for end if end
(Huom. lisätaulukon l on oltava vähintään yhtä suuri kuin taulukon t. Algoritmi järjestää kaikki parametrien 'alku' ja 'loppu' rajaamilla indekseillä olevat alkiot, koko taulukon järjestämiseen on algoritmia kutsuttava komennolla Lomituslajittelu(t,l,1,taulukon t alkioiden lukumäärä) )
Esimerkkitoteus C-kielellä
Lajittelee yhteen suuntaan linkitetyn listan nousevaan järjestykseen, ”cmp” vertailufunktion osoite, ”t_node” typedef linketetyn listan elementin toteuttavalle rakenteelle (struct).
void mergesort(t_node **a, int (*cmp)(void *b, void *c)) { t_node *t; t_node *u; if (a != NULL && *a != NULL && (*a)->next != NULL) { u = split_list(*a); mergesort(a, cmp); mergesort(&u, cmp); t = *a; if ((*cmp)(t, u) > 0) *a = u; merge_lists(t, u, cmp); } } int list_size(t_node *a) { register int i; i = 0; while (a != NULL) { a = a->next; i++; } return (i); } t_node *split_list(t_node *a) { register int i; register int size; t_node *u; size = list_size(a); i = 0; while (i < size / 2 - 1) { a = a->next; i++; } u = a->next; a->next = NULL; return (u); } void roll_merge(t_node **r, t_node **v) { (*v)->next = *r; *v = (*v)->next; *r = (*r)->next; } void merge_lists(t_node *t, t_node *u, int (*cmp)(void *b, void *c)) { t_node *v; v = t; if ((*cmp)(t, u) > 0) { v = u; u = u->next; } else t = t->next; while (t != NULL && u != NULL) { if ((*cmp)(t, u) > 0) roll_merge(&u, &v); else roll_merge(&t, &v); } if (u == NULL) v->next = t; else v->next = u; }