When does a bubble sort stop?

After a pass in which no swaps are made.

What is the middle item position for N odd, and for N even?

\frac{N+1}{2} for odd N; \frac{N+2}{2} for even N.

What is the pivot in quick sort here?

The middle item of the list or sub-list being sorted.

Describe one pass of quick sort.

Write items smaller than the pivot to the left and larger to the right, in their original order; the pivot is then in position.

When does quick sort stop?

When every sub-list has at most one item.

Describe binary search.

Compare with the middle item and discard that item and the half that cannot contain the target; repeat until found or nothing remains.

If the target is smaller than the middle item in a binary search, what is discarded?

The middle item and all items after it.

How do you show a target is not in the list in a binary search?

Continue until no items remain.

Sorting and searching algorithmsEdexcel International A Level Maths: Flashcards

Card 1 of 130 of 13 known

Question

Describe one pass of a bubble sort.

Tap or press Space to reveal

Tap card or press Space to flip

See all 13 cards

Describe one pass of a bubble sort.: Compare adjacent items from the left and swap them if they are in the wrong order, to the end of the list.
After a bubble-sort pass, where is the largest item?: At the end of the list.
When does a bubble sort stop?: After a pass in which no swaps are made.
What is the middle item position for $N$ odd, and for $N$ even?: $\frac{N+1}{2}$ for odd $N$ ; $\frac{N+2}{2}$ for even $N$ .
Which item is the middle item of a list of 10?: The 6th item.
What is the pivot in quick sort here?: The middle item of the list or sub-list being sorted.
Describe one pass of quick sort.: Write items smaller than the pivot to the left and larger to the right, in their original order; the pivot is then in position.
When does quick sort stop?: When every sub-list has at most one item.
What must be true of a list before a binary search?: It must be in order.
Describe binary search.: Compare with the middle item and discard that item and the half that cannot contain the target; repeat until found or nothing remains.
If the target is smaller than the middle item in a binary search, what is discarded?: The middle item and all items after it.
How many comparisons does a bubble-sort pass make on $n$ items?: $n-1$ (fewer on later passes).
How do you show a target is not in the list in a binary search?: Continue until no items remain.

Exam questions on Sorting and searching algorithms

The list 15, 8, 23, 4, 16, 9 is to be sorted into ascending order using a bubble sort. In each pass, adjacent items are compared from the left and swapped if they are in the wrong order.
Find the total number of swaps needed to sort the list.2 marks
The list 31, 12, 45, 7, 28, 19, 52, 3, 36, 24 is to be sorted into ascending order using quick sort. The pivot is always the middle item of the list being sorted. If a list has $N$ items, its middle item is in position $\frac{N+1}{2}$ when $N$ is odd and $\frac{N+2}{2}$ when $N$ is even. In each pass, items smaller than the pivot are written to its left and items larger than the pivot to its right, keeping their original order.
For the sub-list to the right of the first pivot, write down the next pivot and the sub-lists it creates.2 marks
The numbers 3, 8, 12, 17, 21, 25, 29, 34, 38, 42, 47, 53, 60 are in ascending order and are to be searched using a binary search for a number $T$ . The middle item of a list of $N$ items is in position $\frac{N+1}{2}$ if $N$ is odd and $\frac{N+2}{2}$ if $N$ is even. If $T$ is smaller than the middle item, the middle item and all items after it are discarded. Otherwise the middle item and all items before it are discarded. The search stops when $T$ is found or no items remain.
Use the binary search to find $T=42$ , stating the middle item chosen at each stage.3 marks

See the full worksheet

Written by the Exaim team, led by Shaun Daswani (Head of Upper Secondary, Improve ME Institute; MSc Financial Mathematics, Imperial College London; BSc, UCL) and Jason Daswani (operational lead, Improve ME Institute; LSE).