Mullsortimine

Allikas: Vikipeedia
Jump to navigation Jump to search
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. Sorditavat loendit läbitakse korduvalt ja läbimisel vahetatakse kõrvutiasetsevad elemendid, kui need on vales järjestuses. Loend loetakse sordituks, kui läbimise käigus ei tehta ühtegi vahetust. Algoritm on nimetuse 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 sorditavate elementide hulk. On palju sortimisalgoritme, mille halvima või keskmise juhu jõudlus on oluliselt parem, nt O(n log n). Seega pole mullimeetod suure n väärtuse korral otstarbekas.

Mullimeetodi eelis paljude teiste sortimisalgoritmide (sh kiirsortimise) ees on suutlikkus kiiresti tuvastada olukord, kus loend on juba sorditud. Mullsortimise keerukus juba sorditud 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 algusse 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 paksus kirjas.

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 loendi sorditud 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 pole seda veel tuvastanud 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 ja see 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, kui arvestada, 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 sorditud ja neid enam läbima ei pea. Näiteks suurusega n loendi korral on n-is element on oma lõplikul positsioonil pärast esimest läbimist. Teisel läbimisel jääb sortida n - 1 elementi. Pärast teist läbimist on element n - 1 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 mõistmise ja teostamise seisukohalt üks lihtsamaid sortimisalgoritme, pole see ajalise keerukuse O(n2) tõttu tõhus, et kasutada seda mõnest elemendist suuremate loendite korral. Isegi teiste lihtsate O(n2) sortimisalgoritmide hulgas on üldjuhul tõhusamaid algoritme, näiteks vahelepanekuga sortimine.

Tänu oma lihtsusele kasutatakse mullsortimist tihti algajatele arvutiteaduse tudengitele algoritmi või sortimisalgoritmi kontseptsiooni tutvustamiseks. 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]