Bubble sort is the first sorting algorithm that you learn in many algorithm classes.

It's not a particularly fast technique, so it's never really used in practice. And generally if you're writing your own sorting algorithm instead of relying on one that your platform provides then you've made some poor decisions.

However bubble sort is simple enough that anyone can understand it, and most programmers can implement it or verify it.

Preparing for visualization

Before we get to the algorithm itself we need to create some useful functions for visualizing what it does.

We're going to be sorting a list of randomly selected numbers. So we'll need a way to visualize an array of numbers.

For this we'll make a simple bar graph. We'll need functions for drawing lines, for erasing lines, and (building on top of that) for drawing arrays of lines.

;export drawing
to bar :side_a :side_b
  penwidth :side_b/2
  fd :side_a 
  back :side_a
  pu
  rt 90
  fd :side_b
  lt 90
  pd
end

to blank :side_b
  color [255 255 255]
  bar 500 :side_b
  pu 
  lt 90
  fd :side_b
  rt 90
  pd
end


to min :a :b
 ifelse :a < :b output :a
 output :b
end

to showList :list :len :n
  setxy 0 500
  make "index 0
  make "b divide 500 :len
  make "b int :b + 1
  make "prev 0
  repeat min :len :n+1 [
    blank :b
    color [0 250 :index*3]
    if (item :index :list) < :prev
       color [250 0 :index*3] 
    bar item :index :list :b
    make "prev (item :index :list)
    make "index :index + 1
  ]
end

Initializing a random list

Now we need a function for generating a list of random numbers.

;export generateList

to generateList :len
  make "list []
  make "index 0
  repeat :len [
    make "val rand 501
    setitem :index :list :val
    make "index :index + 1
  ]
  output :list  
end

And finally we're onto the bubble sort algorithm itself.

Structurally it's a loop, with an inner loop (i.e a nested loop). In the inner loop it compares two adjacent items from the list. If the first one is bigger than the second one, it's swaps them.

;export bubblesort
;import drawing

to bubblesort :list :len
  make "n :len
  repeat :len - 1 [
    make "i 0
    repeat :n - 1 [
      make "A1 item :i :list
      make "A2 item :i + 1 :list
      if :A1 > :A2 
        [
          SETITEM :i :list :A2        
          SETITEM :i + 1 :list :A1  
        ]
      make "i :i + 1
    ]
    showList :list :len :n
    make "n :n - 1
  ]
end

;import bubblesort
;import generateList

make "len 20 + rand 20
make "list generateList :len
showList :list :len :len

bubblesort :list :len 

External Links

• Wikipedia: Bubble Sort
• Algorithmist: Bubble Sort
• Sorting-Algorithms: Bubble Sort

See Also

• Sorting algorithms