Algorithms Worked Solutions — Further Maths Maths

Question 1

The list 8, 3, 5, 1, 9, 4 is to be sorted into ascending order. A bubble sort is used. In each pass the adjacent pairs are compared from left to right and are swapped if they are in the wrong order. After the first pass the largest item is in its final place, so each pass compares one fewer pair than the pass before. The sort stops when a pass produces no swaps, or when only one item remains to be placed. Which of the following is the list after the first pass?

Accepted Answer

Write down the list to be sorted: L=8, 3, 5, 1, 9, 4
State the list at the end of pass 1: after pass 1: 3, 5, 1, 8, 4, 9
Select the option that gives the list after the first pass: 3, 5, 1, 8, 4, 9
Answer: 3, 5, 1, 8, 4, 9

Question 2

The list 5, 2, 7, 3, 6 is to be sorted into ascending order. A bubble sort is used. In each pass the adjacent pairs are compared from left to right and are swapped if they are in the wrong order. After the first pass the largest item is in its final place, so each pass compares one fewer pair than the pass before. The sort stops when a pass produces no swaps, or when only one item remains to be placed. How many swaps are made in the first pass?

Accepted Answer

Write down the list to be sorted: L=5, 2, 7, 3, 6
State the list at the end of pass 1: after pass 1: 2, 5, 3, 6, 7
State the number of swaps made in the first pass: swaps in pass 1=3
Answer: 3

Question 3

The list 9, 4, 6, 2, 8, 1 is to be sorted into ascending order. A bubble sort is used. In each pass the adjacent pairs are compared from left to right and are swapped if they are in the wrong order. After the first pass the largest item is in its final place, so each pass compares one fewer pair than the pass before. The sort stops when a pass produces no swaps, or when only one item remains to be placed. How many comparisons are made in the first pass?

Accepted Answer

Write down the list to be sorted: L=9, 4, 6, 2, 8, 1
Pass 1: compare every adjacent pair from left to right: comparisons=5,=5
State the list at the end of pass 1: after pass 1: 4, 6, 2, 8, 1, 9
State the number of comparisons made in the first pass: comparisons in pass 1=5
Answer: 5

Question 4

The list 6, 2, 9, 4, 7 is to be sorted into ascending order. A bubble sort is used. In each pass the adjacent pairs are compared from left to right and are swapped if they are in the wrong order. After the first pass the largest item is in its final place, so each pass compares one fewer pair than the pass before. The sort stops when a pass produces no swaps, or when only one item remains to be placed. Which of the following is the list after the first pass?

Accepted Answer

Write down the list to be sorted: L=6, 2, 9, 4, 7
State the list at the end of pass 1: after pass 1: 2, 6, 4, 7, 9
Select the option that gives the list after the first pass: 2, 6, 4, 7, 9
Answer: 2, 6, 4, 7, 9

Question 5

The list 7, 3, 9, 1, 5, 8 is to be sorted into ascending order. A quick sort is used. The first item of each sub-list is chosen as the pivot. The items smaller than the pivot are written, in their original order, to the left of the pivot and the items larger than the pivot are written, in their original order, to its right, so the pivot reaches its final position. In each pass a pivot is chosen from every sub-list containing two or more items; a sub-list containing a single item is already in place and no pivot is chosen from it. Which of the following is the list after the first pass?

Accepted Answer

Write down the list to be sorted: L=7, 3, 9, 1, 5, 8
State the list at the end of pass 1: after pass 1: 3, 1, 5, 7, 9, 8
Select the option that gives the list after the first pass: 3, 1, 5, 7, 9, 8
Answer: 3, 1, 5, 7, 9, 8

Algorithms Worked Solutions — Further Maths Maths

Worked solution

Worked solution

Worked solution

Worked solution

Worked solution

Unlock 65 more Algorithms questions

More Algorithms practice

Related Decision Maths topics