Scratch Programming
Bubble Sort
Introduction
Sorting data is a key task in computer programming. Over the years, many algorithms have been written that achieve this task, all with varying degrees of efficiency. The bubble sort is one of the techniques that is most straightforward to implement.
Here is a pseudocode algorithm for the Bubble Sort,
Repeat
swapflag = false
For count = 1 To N - 1
If bubbleItem[count]>bubbleItem[count + 1] Then
temp = bubbleItem[count]
bubbleItem[count] = bubbleItem[count + 1]
bubbleItem[count + 1] = temp
swapflag = true
End If
Next
N = N - 1
Until swapflag = false Or N = 1
The Code
This first section of code runs when the green flag is clicked and creates a list of 10 random numbers.
This section of code performs the bubble sort with some pausing and output to show what is happening to the numbers in the list as they are sorted.
The two cat sprites have similar scripts, the cat on the right just does the sorting without talking.
You can download the program too - bubble sort.sb
Challenges
There are lots of different ways to sort data in a list. Here are some pseudocode descriptions of some of them,
Insertion Sort
For outerLoop = 1 To arrayLength - 1
temp = item[outerLoop]
innerLoop = outerLoop
While (innerLoop > 0 And item[innerLoop - 1] >= temp)
item[innerLoop] = item[innerLoop - 1]
innerLoop = innerLoop - 1
End While
item[innerLoop] = temp
Next outerLoop
Selection Sort
For outerLoop = 0 To arrayLength - 2
minValue = outerLoop
For innerLoop = outerLoop + 1 To arrayLength - 1
If item[innerLoop] < item[minValue] Then minValue = innerLoop
Next innerLoop
temp = item[outerLoop]
item[outerLoop] = item[minValue]
item[minValue] = temp
Next outerLoop
Shell Sort
h = 1
While (h<=arrayLength/3)
h = h * 3 +1
End While
While (h > 0)
For outerLoop = h To arrayLength - 1
temp = item[outerLoop]
innerLoop = outerLoop
While (innerLoop > h - 1 And item[innerLoop - h] >= temp)
item[innerLoop] = item[innerLoop - h]
innerLoop = innerLoop - h
End While
item[innerLoop] = temp
Next outerLoop
h = (h - 1)/3
End While
These are all quite tricky to implement. Have a go at whichever one takes your fancy and test that it actually sorts the data correctly. Then use a list with more numbers and compare the speed of each algorithm.