wiki. secretGeekBubble Sort
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