Mullsortimine

Mullsortimine

Mullsortimist demonstreeriv animatsioon
Algoritmi liik	Sortimisalgoritm
Ajaline keerukus halvimal juhul	$O(n^{2})$
Ajaline keerukus keskmiselt	$O(n^{2})$
Ajaline keerukus parimal juhul	$O(n)$
Mahuline keerukus	$O(1)$

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

Nii halvimal kui ka keskmisel juhul on mullimeetodi keerukus O(n²), 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

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

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 ) $\to$ ( 1 8 5 2 4 ) Algoritm võrdleb kahte esimest elementi ning vahetab nende järjestuse, kuna 8 > 1
( 1 8 5 2 4 ) $\to$ ( 1 5 8 2 4 ) Vahetus, kuna 8 > 5
( 1 5 8 2 4 ) $\to$ ( 1 5 2 8 4 ) Vahetus, kuna 8 > 2
( 1 5 2 8 4 ) $\to$ ( 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 ) $\to$ ( 1 5 2 4 8 ) Kuna elemendid on juba õiges järjestuses (1 < 5), siis vahetust ei toimu
( 1 5 2 4 8 ) $\to$ ( 1 2 5 4 8 ) Vahetus, kuna 5 > 2
( 1 2 5 4 8 ) $\to$ ( 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 ) $\to$ ( 1 2 4 5 8 )
( 1 2 4 5 8 ) $\to$ ( 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

Pseudokood

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

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 $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 kahanevas järjestuses) on mullimeetod selle täiendusega kaks korda kiirem.

C

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

Kuigi mullsortimine on mõistmise ja teostamise seisukohalt üks lihtsamaid sortimisalgoritme, pole see ajalise keerukuse O(n²) tõttu tõhus, et kasutada seda mõnest elemendist suuremate loendite korral. Isegi teiste lihtsate O(n²) sortimisalgoritmide hulgas on üldjuhul tõhusamaid algoritme, näiteks vahelepanekuga sortimine.

Tänu lihtsusele kasutatakse mullsortimist tihti algajatele arvutiteaduse üliõpilastele 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.

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

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