Lomituslajittelu
Wikipedia
Lomituslajittelu (lomitusjärjestäminen, Merge sort) on asymptoottiselta suoritusajaltaan tehokas (Θ(n log n)) 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
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 jommassa kummassa 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ä) )
