Lomituslajittelu

Wikipedia
Loikkaa: valikkoon, hakuun

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:

  1. Jaa taulukko kahteen yhtä suureen osataulukkoon
  2. Järjestä osataulukot rekursiivisesti
  3. 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 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ä[muokkaa | muokkaa wikitekstiä]

Lajittelee yhteen suuntan linkitetyn listan nousevaan järjestykseen, "cmp" vertailufunktion osoite.

void Mergesort(struct lista **a, int (*cmp)(void *a, void *b)) {
    if(a) {
        struct lista *b1=(*a);
        int c=1, i=0;
        while(b1->next)
            b1=b1->next, c++;
        if(c>1) {
	    b1=(*a);
	    for(i=1; i<c/2; i++)
	        b1=b1->next;
            struct lista *b2 = b1->next, *b3;
	    b1->next=NULL;
            Mergesort(a, cmp);
	    Mergesort(&b2, cmp);
	    b3=(*a);
	    while(b2) {
	        if(cmp(b3,b2)>0) {
		    if(b3==(*a)) {
		         (*a)=b2;
		         b2=b2->next;
		         (*a)->next=b3;
		    }
		    else {
		        struct lista *b4 = (*a);
		        while(b4->next != b3)
                            b4=b4->next;
		        b4->next=b2;
		        b2=b2->next;
		        b4->next->next=b3;
		    }
		continue;
		}
	        else {
		    while(b3->next && cmp(b3->next,b2)<0)
		        b3=b3->next;
		    if(!b3->next) {
		        b3->next=b2;
		        break;
		    }
		    else {
		        struct lista *b5 = b3->next;
		        b3->next=b2;
		        b2=b2->next;
		        b3->next->next=b5;
		        continue;
		    }
                }
	    break;
	    }
        }
    }
}