Kuplalajittelu

Kuplalajittelu (engl. bubble sort) on erittäin hidas (O(n²)) lajittelualgoritmi, jolla ei ole etuja nopeampiin algoritmeihin edes muistinkäytön suhteen. Se toimii seuraavasti:

1. Käydään jono läpi vertaillen kutakin jonon peräkkäistä kahta alkiota toisiinsa. Jos ne ovat väärässä järjestyksessä, vaihdetaan ne keskenään.
2. Mikäli vaihtoja tehtiin, toistetaan ensimmäinen vaihe.

Kuplalajittelu voidaan toteuttaa esimerkiksi seuraavalla Python-kielisellä koodilla:

def bubblesort(a):
    """bubblesort(a) -> list
    Järjestää taulukon a järjestykseen pienimmästä suurimpaan.
    """
    # Tähän muuttujaan tallennetaan tieto siitä, onko vaihtoja tehty
    changes = True
    # Toistetaan niin kauan, kuin vaihtoja tulee
    while changes:
        changes = False
        # Iteroidaan järjestettävän taulukon yli
        for i in xrange(1, len(a)):
            # Tarkistetaan alkioiden järjestys
            if a[i] < a[i - 1]:
                # Alkiot ovat väärin päin, joten vaihdetaan ne keskenään
                a[i], a[i - 1] = a[i - 1], a[i]
                # Vaihto on tapahtunut, joten iterointi on toistettava
                changes = True
    # Se, että olemme päässeet tähän kohtaan koodia, tarkoittaa että
    # taulukko on järjestyksessä; palautetaan se siis kutsujalle
    return a

Esimerkkitoteutus C-kielellä

#include <stdio.h>
#include <stdlib.h>
 
void swap(void *valkio1, void *valkio2, int koko) /* kahden alkion paikkojen vaihtoa varten */
{
  if(koko > 0)
    {
      char *apu;
      if((apu=(char *)malloc(koko))!=NULL)
        {
          int i1=0;
          for(i1=0; i1<koko; i1++)
            *(apu+i1)=*((char *)valkio2+i1);
          for(i1=0; i1<koko; i1++)
            *((char *)valkio2+i1)=*((char *)valkio1+i1);
          for(i1=0; i1<koko; i1++)
            *((char *)valkio1+i1)=*(apu+i1);
          free(apu);
          apu=NULL;
        }
    }
}
 
void bubblesort(void *alkio, int lkm, int koko, int (*cmp)(void *valkio1, void *valkio2))
{
  if(alkio != NULL && lkm > 1 && koko > 0) /* jonkinlaiset järkevät alkuehdot */
    {
      int i1=0;
      for(i1=0; i1<lkm-1; i1++)
        {
          if(cmp((char *)alkio+i1*koko, (char *)alkio+(i1+1)*koko) < 0)
            {
              int i2=i1-1;
              swap((char *)alkio+i1*koko, (char *)alkio+(i1+1)*koko, koko);
              while(i2>=0 && cmp((char *)alkio+i2*koko, (char *)alkio+(i2+1)*koko)<0)
                {
                  swap((char *)alkio+i2*koko, (char *)alkio+(i2+1)*koko, koko);
                  i2--;
                }
            }
        }
    }
}

Aiheesta muualla

• NIST:in kuvaus kuplalajittelusta