Further algorithms - EdexcelBubble sort

A bubble sort is the simplest of the sorting algorithms. However, it is an inefficient sort for anything but a small list because of the number of comparisons required.

A written description algorithm of a bubble sort is:

1. Start at the beginning of the list.
2. Compare the first value in the list with the next one up. If the first value is bigger, swap the positions of the two values.
3. Move to the second value in the list. Again, compare this value with the next and swap if the value is bigger.
4. Keep going until the there are no more items to compare. Note - the last item checked in the list is now sorted, so ignore this next time.
5. Go back to the start of the list.

Each run through the list, from start to finish, is known as a pass. The bubble sort continues until a pass is made where no values have been swapped. At this point, the list is sorted.

Consider this unsorted list:

The value at position 0 is 9, and the value at position 1 is 4. 9 is bigger than 4, so the two items are swapped. The list is now:

Then move up to the next position, position 1. The value at position 1 is 9, and the value at position 2 is 2. 9 is bigger than 2, so the two items are swapped. The list is now:

Move up to the next position, position 2. The value at position 2 is 9, and the value at position 3 is 6. 9 is bigger than 6, so the two items are swapped. The list is:

Now move up to the next position, position 3. The value at position 3 is 9, and the value at position 4 is 5. 9 is bigger than 5, so the two items are swapped. The list is now:

The first pass is now complete. However, this list may still be unsorted, so another pass takes place.

After the second pass, the list is now:

The second pass is now complete. However, this list may still be unsorted, so another pass takes place.

After the third pass, the list is the same, as all items were in order after the second pass. However, a bubble sort continues until no swaps are made in a pass. During the third pass, no swaps occurred, so now the sort knows that all items are in order.

A pseudo-code algorithm for a bubble sort might be:

SET counter TO 0 SET swapped TO True SET swaps TO 0 SET length TO LENGTH(list) WHILE swapped = True DO WHILE counter < length – 1 DO IF list[counter] > list[counter + 1] THEN SET temp TO list[counter] SET list[counter] TO list[counter + 1] SET list[counter + 1] TO temp SET swaps TO swaps + 1 END IF SET counter TO counter + 1 SET length TO length - 1 END WHILE IF swaps = 0 THEN SET swapped TO False ELSE SET swaps TO 0 SET counter TO 0 END IF END WHILE