# 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.