Mullsortimine

Allikas: Vikipeedia
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[muuda | redigeeri lähteteksti]

Nii halvima kui ka keskmise juhtumi korral on mullimeetodi jõudluseks O(n2), 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[muuda | redigeeri lähteteksti]

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[muuda | redigeeri lähteteksti]

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[muuda | redigeeri lähteteksti]

Lahendus pseudokoodis[muuda | redigeeri lähteteksti]

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[muuda | redigeeri lähteteksti]

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[muuda | redigeeri lähteteksti]

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[muuda | redigeeri lähteteksti]

Kuigi mullsortimine on üks lihtsamaid sortimisalgoritme nii mõistmiseks kui ka implementeerimiseks, muudab O(n2) keerukus selle liiga ebaefektiivseks, et kasutada seda loendite korral, mis on pikemad kui mõned elemendid. Isegi teiste lihtsate O(n2) 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.[1]

Viited[muuda | redigeeri lähteteksti]

  1. Owen Astrachan. Bubble Sort: An Archaeological Algorithmic Analysis. SIGCSE 2003 Hannan Akhtar . (pdf)

Kirjandus[muuda | redigeeri lähteteksti]

  • 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[muuda | redigeeri lähteteksti]