Mullsortimine
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.
Mullsortimist demonstreeriv animatsioon | |
Algoritmi liik | Sortimisalgoritm |
---|---|
Ajaline keerukus halvimal juhul | |
Ajaline keerukus keskmiselt | |
Ajaline keerukus parimal juhul | |
Mahuline keerukus |
Jõudlus
muudaNii 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
muudaMullimeetodi 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
muudaAntud 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
muudaPseudokood
muudaAlgoritmi 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
muudaMullimeetodi 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
muudaNä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
muudaKuigi 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 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.[1]
Viited
muudaKirjandus
muuda- 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- Animated Sorting Algorithms: Bubble Sort – graafiline demonstratsioon ja arutelu mullsortimisest
- Animatsioon, mis tutvustab mullsortimist ja kiirsortimist ning võrdleb nende jõudlust