Searching and sorting algorithms - OCRStandard sorting algorithms

Methods of sorting include:

• bubble sort
• merge sort
• insertion sort

Bubble sort

A bubble sort is the simplest of the sorting algorithms.

Bubble sorts work like this:

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 there are no more items to compare.
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.

Example

Step one

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 would be swapped. The list would now be:

Step two

We 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 would be swapped. The list would now be:

Step three

We 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 would be swapped. The list would now be:

Step four

We 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 would be swapped. The list would now be:

Step five

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

After the second pass, the list would be:

Step six

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

After the third pass, the list would be 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 pseudocode algorithm for a bubble sort might be:

counter = 0
swapped = True
swaps = 0
length = list.length
while swapped == True while counter < length-1 if list[counter] > list[counter+1] then temp = list[counter] list[counter] = list[counter+1] list[counter+1] = temp swaps = swaps + 1 endif counter = counter + 1 endwhile if swaps == 0 then swapped = False else: swaps = 0 counter = 0 endif
endwhile