Standard Sorting Algorithms

Question 1

What happens in a bubble sort?

Answer 1

• We look at two pieces of data in turn.
• We rearrange these two pieces of data (if needed) before moving onto the next two pieces of data.
• Each time we go from the start of the data set to the end we call it a pass.
• We cannot stop passing through the data set until we pass through it and move no pieces of data.

Question 2

Example - rearrange the below data set so its in order from smallest to largest: 75, 10, 26, 97, 68

Answer 2

FIRST PASS:
- Swap 75 and 10 (10, 75, 26, 97, 68)
- Swap 75 and 26 (10, 26, 75, 97, 68)
- Don’t swap 75 and 97
- Swap 97 and 68 (10, 26, 75, 68, 97)

SECOND PASS:
- Swap 75 and 68 (10, 26, 68, 75, 97)

THIRD PASS (we moved data so needs to be done again) -
- Change nothing.
- Three passes

Question 3

What happens in a merge sort?

Answer 3

• We break our data set up into pairs to start off with.
• We re-arrange these pairs and then begin to merge these pairs together.
• We repeat this process until we merge the whole data set back together and re-arrange that.

Question 4

Example - Rearrange (75, 10, 26, 97, 68) using a merge sort.

Answer 4

• Break up the list into pairs (68 is ok on its own)
• Swap 10 and 75
• Don’t swap 26 and 97
• Don’t swap 68 and nothing
• Merge the two nearest pairs from the left together
• 10, 26, 75, 97, 68
• Merge the big list and the 68 together
• Rearrange
• 10, 26, 68, 75, 97

Question 5

What happens in an insertion sort?

Answer 5

• We create a temporary list.
• We work our way through our data set and place each piece of data into the correct location in the temporary list.

Question 6

Use an insertion sort to sort: 75, 10, 26, 97, 68

Answer 6

• 75 is the first term in the temporary list
• 10 is smaller than 75, so it goes to first place in a new list (75 goes to 2)
• 26 slots between 10 and 75
• 97 goes at the end
• 68 goes in the middle.

SHOW EACH INSERTION!