Mullsortimine

Allikas: Vikipeedia
Mullsortimine
Bubble sort animation.gif
Mullsortimist demonstreeriv animatsioon
Algoritmi liik Sortimisalgoritm
Ajaline keerukus halvimal juhul
Ajaline keerukus keskmiselt
Ajaline keerukus parimal juhul
Mahuline keerukus
Mullsortimine sammhaaval

Mullsortimine ehk mullimeetod (inglise k bubble sort) on lihtne sortimisalgoritm. Sorteerivatat loendit läbitakse korduvalt, vahetades kõrvutiasetsevad elemendid, kui need on vales järjestuses. Loend on sorteeritud siis, kui jõutakse läbimiseni, mille käigus ei tehta ühtegi vahetust. 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 | muuda lähteteksti]

Nii halvimal kui ka keskmisel juhul on mullimeetodi keerukus O(n2), kus n on sorteeritavate elementide hulk. On palju sortimisalgoritme, mille halvima või keskmise juhu jõudlus on oluliselt parem, nt O(n log n). Seega pole mullimeetod otstarbekas, kui n on suur.

Siiski on mullimeetodil üks eelis paljude teiste sortimisalgoritmide (isegi kiirsortimise) ees. Mullimeetod tuvastab kiiresti olukorra, kus loend on juba sorteeritud. Mullsortimise keerukus juba sorteeritud loendi korral (parim juhtum) on O(n). Selline omadus on ka näiteks vahelepanemisega sortimisel.

Mullimeetod on stabiilne ja töötab kohapeal ehk ei vaja lisamälu.

Küülikud ja kilpkonnad[muuda | muuda lähteteksti]

Mullimeetodi jõudluse määrab suuresti elementide asetus. Suuri elemente loendi alguses vahetatakse tihti, seega liiguvad need kiiresti oma õigele kohale. Väikesed elemendid loendi lõpus liiguvad algusesse aga väga aeglaselt. Selliseid elemente on hakatud kutsuma vastavalt küülikuteks ja kilpkonnadeks.

Sammhaaval näide[muuda | muuda lähteteksti]

Antud on loend elementidega 8, 1, 5, 2 ja 4, mida sorditakse mullimeetodil väiksemast suuremani. Igal sammul on võrreldavad elemendid kirjutatud rasvaselt.

Esimene läbimine:
( 8 1 5 2 4 ) ( 1 8 5 2 4 ) Algoritm võrdleb kahte esimest elementi ning vahetab nende järjestuse, kuna 8 > 1
( 1 8 5 2 4 ) ( 1 5 8 2 4 ) Vahetus, kuna 8 > 5
( 1 5 8 2 4 ) ( 1 5 2 8 4 ) Vahetus, kuna 8 > 2
( 1 5 2 8 4 ) ( 1 5 2 4 8 ) Vahetus, kuna 8 > 4
Igal läbimisel "mullitab" võrreldud elementidest suurim õigesse kohta lõplikus järjestuses. See tähendab, et igal järgmisel läbimisel tuleb võrrelda ühe võrra vähem elemente.

Teine läbimine:
( 1 5 2 4 8 ) ( 1 5 2 4 8 ) Kuna elemendid on juba õiges järjestuses (1 < 5), siis vahetust ei toimu
( 1 5 2 4 8 ) ( 1 2 5 4 8 ) Vahetus, kuna 5 > 2
( 1 2 5 4 8 ) ( 1 2 4 5 8 ) Vahetus, kuna 5 > 4
Nüüdseks on loend sorditud, kuid algoritm seda veel ei tea ja jätkab.

Kolmas läbimine:
( 1 2 4 5 8 ) ( 1 2 4 5 8 )
( 1 2 4 5 8 ) ( 1 2 4 5 8 )
Algoritm lõpetab töö, kuna sellel läbimisel ei tehtud ühtegi vahetust, mis tähendab, et loend on sorditud.

Implementatsioonid[muuda | muuda lähteteksti]

Pseudokood[muuda | muuda lähteteksti]

Algoritmi võib esitada kujul:

procedure bubbleSort( A : list of sortable items )
  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

Jõudluse parandus[muuda | muuda lähteteksti]

Mullimeetodi jõudlust saab parandada pannes tähele, et pärast igat läbimist jõuab võrreldud elementidest suurim oma lõplikule kohale loendi lõpuosas. Loendi lõppu jõudnud elemendid on sorteeritud ja neid enam läbima ei pea. 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.

procedure bubbleSort( A : list of sortable items )
  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 võrdlust, tehakse maksimaalselt võrdlust. Täitmisaeg on ikka , kuid halvimal juhul (sisendandmed on kahanevas järjestuses) on mullimeetod selle täiendusega kaks korda kiirem.

C[muuda | muuda lähteteksti]

Näidislahendus C-s:

void bubbleSort(int numbers[], int numbers_size) {
    int n, i;
    for (n = numbers_size - 1; n > 0; n--) {
        for (i = 1; i <= n; i++) {
            int left = numbers[i - 1];
            int right = numbers[i];
            if (left > right) {
                numbers[i - 1] = right;
                numbers[i] = left;
            }
        }
    }
}

int numbers[] = { 8, 1, 5, 2, 4 };
bubbleSort(numbers, 5);

Praktiline kasutus[muuda | muuda lähteteksti]

Kuigi mullsortimine on üks lihtsamaid sortimisalgoritme, mida mõista ja implementeerida, on see ajalise keerukuse O(n2) tõttu liiga ebaefektiivne, 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.

Tänu oma lihtsusele kasutatakse mullsortimist tihti selleks, et algajatele arvutiteaduse tudengitele tutvustada algoritmi või sortimisalgoritmi kontseptsiooni. Samas on mõned arvutiteadlased, näiteks Owen Astrachan, vastu mullsortimise kasutamisele ja õpetamisele, kuna see leiab praktikas vähe kasutust.[1]

Viited[muuda | muuda lähteteksti]

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

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