Bubble sort

Bubble Sort

Ang bubble sort (literal sa Tagalog: pag-uuring bula) ay isang uri ng algoritmong pag-uuri. Isinasagawa ito sa pamamagitan ng paghahambing sa mga magkakatabing numero sa isang listahan.

Nagsisimula ang paghahambing mula sa una at pangalawang numero sa listahan. Kapag ang naunang numero ay mas mataas kaysa sa ikalawang numero, sila ay pagpapalitin at ihahambing muli ang unang numero sa sumunod (ikatlong) numero. Patuloy na gagawin ang nasabing hakbang hanggat mas mataas ang naunang numero sa sumunod na numero sa listahan.

Kapag hindi na maaring pagpalitin ang dalawang numero, ang sumunod na numero naman ang ihahambing sa kasunod nitong numero sa listahan. Gagawin ang hakbang na ito hanggang ang sa marating ang dulo ng listahan. Kapag nangyari ito, magsisimula ulit ang paghahambing mula sa unahan ng listahan (bagong una at ikalawang numero). Uulitin ang mga nasabing hakbang hanggang sa ang lahat ng numero sa listahan ay nasa tamang posisyon na sa listahan.

Ang bubble sort ay isa sa pinakasimple at madaling intindihin na algoritmong pag-uuri. Gayunpaman, ito ay hindi magandang gamitin lalong-lalo na sa malalaking listahan sapagkat matagal itong matapos.

Ang bubble sort ay pinakamainam gamitin kapag ang listahan ay halos ayos na kung saan marami sa mga numero ay nasa tamang posisyon na.

Ang pangkaraniwan at malalang kaso ng algoritmong ito ay O(n²).

Halimbawa:

4 3 5 2 1
3 4 5 2 1
3 4 2 5 1
3 4 2 1 5
3 2 4 1 5
3 2 1 4 5
2 3 1 4 5
2 1 3 4 5
1 2 3 4 5

Pseudocode:

procedure bubbleSort( A : list of sortable items )
   n = length(A)
   repeat 
     swapped = false
     for i = 1 to n-1 inclusive do
       /* if this pair is out of order */
       if A[i-1] > A[i] then
         /* swap them and remember something changed */
         swap( A[i-1], A[i] )
         swapped = true
       end if
     end for
   until not swapped
end procedure

Mga sanggunian

algolist.com
binternet.co.uk
comp.dit.ie Naka-arkibo 2010-12-24 sa Wayback Machine.