Mullsortimine

Mullsortimist demonstreeriv animatsioon.

Mullsortimine ehk mullimeetod (Bubble sort) on lihtne sortimisalgoritm. See töötab sorteeritavat loendit korduvalt läbides, võrreldes igat paari kõrvutiasetsevaid elemente ning vahetab need omavahel, kui need on vales järjestuses. Loendit läbitakse senikaua, kuni ühtegi vahetust ei ole vaja enam teha, mis näitab, et elemendid on õiges järjestuses. Algoritm on oma nime saanud selle järgi, kuidas igal läbimisel üks element jõuab vahetamiste käigus oma õigele kohale – kerkib nagu mull veepinnale.

Jõudlus

Nii halvima kui ka keskmise juhtumi korral on mullimeetodi jõudluseks O(n²), kus n on sorteeritavate elementide hulk. On olemas palju sortimisalgoritme, mille halvima või keskmise juhtumi jõudlus on oluliselt parem: O(n logn). Seega mullimeetod ei ole otstarbekas sortimisalgoritm, kui n on suur.

Siiski on mullimeetodil üks suur eelis paljude teiste (isegi kiirsortimise) sortimisalgoritmide ees: oskus tuvastada juba sorteeritud andmed on seal efektiivselt teostatud. Mullsortimise jõudlus sorteeritud loendi korral (parim juhtum) on O(n).

Küülikud ja kilpkonnad

Elementide asetsus mullimeetodi puhul määrab suuresti ka selle jõudluse. Suured elemendid loendi alguses ei tekita probleeme, kuna nad vahetatakse kiiresti ning seega liiguvad kiiresti ka oma õigele kohale. Väikesed elemendid lõpuosas liiguvad algusesse aga väga aeglaselt. Seda tüüpi elemente on hakatud vastavalt kutsuma küülikuteks ja kilpkonnadeks.

Sammhaaval näide

Olgu meil rida numbritega "5 1 4 2 8" ja sorteerime selle väiksemast suuremani, kasutades mullimeetodit. Igal sammul on võrreldavad elemendid kirjutatud rasvaselt.

Esimene läbimine:
( 5 1 4 2 8 ) $\to$ ( 1 5 4 2 8 ), Siin algoritm võrdleb kahte esimest elementi ning vahetab nende järjestuse.
( 1 5 4 2 8 ) $\to$ ( 1 4 5 2 8 ), Vahetus, kuna 5 > 4
( 1 4 5 2 8 ) $\to$ ( 1 4 2 5 8 ), Vahetus, kuna 5 > 2
( 1 4 2 5 8 ) $\to$ ( 1 4 2 5 8 ), Nüüd, kuna elemendid on juba õiges järjestuses (8 > 5), siis vahetust ei toimu.
Teine läbimine:
( 1 4 2 5 8 ) $\to$ ( 1 4 2 5 8 )
( 1 4 2 5 8 ) $\to$ ( 1 2 4 5 8 ), Vahetus, kuna 4 > 2
( 1 2 4 5 8 ) $\to$ ( 1 2 4 5 8 )
( 1 2 4 5 8 ) $\to$ ( 1 2 4 5 8 )
Nüüdseks on rida sorteeritud, kuid algoritm ei tea, kas sorteerimisega on lõpule jõutud. Algoritm vajab veel ühte täielikku läbimist ilma ühegi vahetuseta, et veenduda, et rida on sorteeritud.
Kolmas läbimine:
( 1 2 4 5 8 ) $\to$ ( 1 2 4 5 8 )
( 1 2 4 5 8 ) $\to$ ( 1 2 4 5 8 )
( 1 2 4 5 8 ) $\to$ ( 1 2 4 5 8 )
( 1 2 4 5 8 ) $\to$ ( 1 2 4 5 8 )
Rida on sorteeritud ning algoritm võib oma töö lõpetada.

Implementatsioon

Lahendus pseudokoodis

Algoritmi võib esitada kujul:

procedure bubbleSort( A : list of sortable items ) defined as:
  do
    swapped := false
    for each i in 0 to length(A) - 2 inclusive do:
      if A[i] > A[i+1] then
        swap( A[i], A[i+1] )
        swapped := true
      end if
    end for
  while swapped
end procedure

Alternatiivsed lahendused

Näidislahendus C's:

void bubbleSort(int numbers[], int array_size)
{
  int i, j, temp;
 
  for (i = (array_size - 1); i > 0; i--)
  {
    for (j = 1; j <= i; j++)
    {
      if (numbers[j-1] > numbers[j])
      {
        temp = numbers[j-1];
        numbers[j-1] = numbers[j];
        numbers[j] = temp;
      }
    }
  }
}

Väike jõudluse parandus

Mullimeetodi jõudlust saab parandada järgmisel viisil. Pärast iga läbimist jõuab suurim element oma kohale loendi lõpus (läbitud osa). Olgu meil loend suurusega n, siis n-is element on oma lõplikul positsioonil pärast esimest läbimist. Seega jääb sorteerida n - 1 elementi. Pärast teist läbimist on n - 1-ne element oma lõplikul positsioonil ja nii edasi. Iga läbimine võib olla ühe sammu võrra lühem, kui eelmine, selle asemel, et igal läbimisel võrrelda viimaseid elemente, mis on juba oma õigetel positsioonidel ning vahetust niikuinii ei toimu.

Võimalik saavutada järgnevalt (pseudokood):

procedure bubbleSort( A : list of sortable items ) defined as:
  n := length( A )
  do
    swapped := false
    for each i in 0 to n - 1  inclusive do:
      if A[ i ] > A[ i + 1 ] then
        swap( A[ i ], A[ i + 1 ] )
        swapped := true
      end if
    end for
    n := n - 1
  while swapped
end procedure

Selle asemel, et teha $n \cdot (n-1)$ võrdlust, tehakse maksimaalselt $(n-1) + (n-2) + \cdots + 1 = \frac{n(n-1)}{2}$ võrdlust. Täitmisaeg on ikka $O(n^2)$, kuid halvimal juhul (sisendandmed on tagurpidi sorteeritud) on mullimeetod selle uuendusega kaks korda kiirem, kui ilma selleta.

Praktiline kasutus

Kuigi mullsortimine on üks lihtsamaid sortimisalgoritme nii mõistmiseks kui ka implementeerimiseks, muudab O(n²) keerukus selle liiga ebaefektiivseks, et kasutada seda loendite korral, mis on pikemad kui mõned elemendid. Isegi teiste lihtsate O(n²) sortimisalgoritmide seas on algoritme, näiteks vahelepanekuga sortimine, mis on üldjuhul märgatavalt efektiivsemad

Oma lihtsuse tõttu kasutatakse tihti just mullsortimist, et algajatele arvutiteaduse tudengitele tutvustada algoritmi või sortimisalgoritmi kontseptsiooni. Mõned teadlased nagu näiteks Owen Astrachan on läinud üsna kaugele, et halvustada mullsortimist ning selle kestvat populaarsust arvutiteaduse hariduses, soovitades peatada selle õpetamine.

Kirjandus

• Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Leheküljed 106–110, paragrahv 5.2.2: Sorteerimine vahetamistega.
• L. Liikane, M. Kesa. Arvutisõnastik. bubble sort.
• V. Hanson, A. Tavast. Arvutikasutaja sõnastik. bubble sort.

Välislingid

• Bubblesort code
• Animated Sorting Algorithms: Bubble Sort – graafikaline demonstratsioon ja arutelu mullsortimisest
• Animatsioon, mis tutvustab mullsortimist ja kiirsortimist ning võrdleb nende jõudlust