Sorting Algorithms

Question 1

Bubble sort

Answer 1

Bubble sort starts at the begginign of the list, and compares pairs of items, swapping them individually into more orderly positions. e.g:

2 1 3 6 5 4
1 2 3 6 5 4 - first 2 are swapped into better positions.
1 2 3 6 5 4 - 2nd two (2 and 3) are fine, no swap needed.
1 2 3 6 5 4 - 3rd two (3 and 6) are fine.
1 2 3 5 6 4 - 4th (6 and 5) two are swapped.
1 2 3 5 4 6 - 6 and 4 are swapped
1 2 3 4 5 6 - 4 and 5 are swapped.

It is known as a bubble sort, because the values ‘bubble’ to the top.

Question 2

Insertion Sort

Answer 2

Insertion sort examines each value in the list, and inserts it into the correct position relative to the rest.

6  3  1  2  5  4
3  6  1  2  5  4 - the 3 was examined, then moved into a suitable position
1  3  6  2  5  4 - the 1 was moved
1  2  3  6  5  4 - the 2 was moved
1  2  3  5  6  4 - the 5 was moved
1  2  3  4  5  6 - the 4 was moved.

This is the same sorting method as sorting playing cards

Question 3

Merge Sort

Answer 3

Merge sort breaks the list up into individual values, and then rebuilds it, essentially.

7,6,8,3,0,5,2,9
7,6,8,3  0,5,2,9
7,6  8,3  0,5  2,9
7  6  8  3  0  5  2  9
6,7  3,8  0,5  2,9