Sorting and searching algorithms

Sorting and searching algorithms Test

Spec 1.2 Ā· Edexcel International A Level Maths: Subtopic test

Studying this course? Keep your progress in one place.

Two ways to do this test

Question by question

One question at a time. Each answer is marked the moment you hand it in, so you learn as you go. Drago helps if you get stuck. All 10 questions, or just 5.

Exam mode

The whole paper in one go, timed like the real exam. Nothing is marked until you hand it in, then you get every mark explained.

10 questions, 27 marks

Edexcel International A Level Maths

Sorting and searching algorithms

Total 27 marks

Name

Class

Date

  1. 1
    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.
    (a)
    What is the list after the first pass?
    [1 mark]
    • A8, 15, 23, 4, 16, 9
    • B4, 8, 9, 15, 16, 23
    • C8, 15, 4, 16, 9, 23
    • D8, 4, 15, 9, 16, 23
    Show the mark scheme

    Mark scheme

    Answer: C
    (b)
    How many passes are needed in total, including the final pass that makes no swaps?
    [1 mark]
    • A33
    • B44
    • C55
    • D66
    Show the mark scheme

    Mark scheme

    Answer: B
    (c)
    Find the total number of swaps needed to sort the list.
    [2 marks]
    Show the mark scheme

    Mark scheme

    M1: swaps per pass 4,2,24, 2, 2 (and 00 in the last pass), at least three correct
    A1:
    88

    Total for question 1: 4 marks

  2. 2
    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 NN items, its middle item is in position N+12\frac{N+1}{2} when NN is odd and N+22\frac{N+2}{2} when NN 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.
    (a)
    Which item is the first pivot?
    [1 mark]
    • A2828
    • B3131
    • C2424
    • D1919
    Show the mark scheme

    Mark scheme

    Answer: D
    (b)
    After the first pass, which items are to the right of the pivot?
    [1 mark]
    • A31, 45, 28, 52, 36, 24
    • B24, 28, 31, 36, 45, 52
    • C24, 36, 52, 28, 45, 31
    • D52, 45, 36, 31, 28, 24
    Show the mark scheme

    Mark scheme

    Answer: A
    (c)
    For the sub-list to the right of the first pivot, write down the next pivot and the sub-lists it creates.
    [2 marks]
    Show the mark scheme

    Mark scheme

    B1: pivot 5252 (4th item of the 6 items)
    B1: left sub-list
    31,45,28,36,2431, 45, 28, 36, 24 and an empty right sub-list

    Total for question 2: 4 marks

  3. 3
    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 TT. The middle item of a list of NN items is in position N+12\frac{N+1}{2} if NN is odd and N+22\frac{N+2}{2} if NN is even. If TT 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 TT is found or no items remain.
    (a)
    Use the binary search to find T=42T=42, stating the middle item chosen at each stage.
    [3 marks]
    Show the mark scheme

    Mark scheme

    B1: first middle item 2929 (7th of 13)
    M1: second middle item
    4747 (4th of the 6 items 34,38,42,47,53,6034, 38, 42, 47, 53, 60)
    A1: third middle item
    3838, then 4242 found
    (b)
    Use the binary search to show that T=20T=20 is not in the list.
    [4 marks]
    Show the mark scheme

    Mark scheme

    M1: first middle item 2929, leaving 3,8,12,17,21,253, 8, 12, 17, 21, 25
    M1: second middle item
    1717 (4th of 6), leaving 21,2521, 25
    A1: third middle item
    2525, leaving 2121, then middle item 2121
    A1: no items remain, so
    2020 is not in the list

    Total for question 3: 7 marks

  4. 4
    The list 27, 14, 35, 8, 22, 41, 11, 19 is to be sorted into ascending order.
    (a)
    Use quick sort, with the middle item as the pivot, to sort the list. If a list has NN items, its middle item is in position N+12\frac{N+1}{2} when NN is odd and N+22\frac{N+2}{2} when NN is even. Show the pivot and the sub-lists at each stage.
    [6 marks]
    Show the mark scheme

    Mark scheme

    B1: first pivot 2222 (5th of 8)
    M1: sub-lists
    14,8,11,1914, 8, 11, 19 and 27,35,4127, 35, 41
    M1: pivots
    1111 (3rd of 4) and 3535 (2nd of 3)
    A1: sub-lists
    88 and 14,1914, 19; 2727 and 4141
    B1: pivot
    1919 for the list 14,1914, 19, giving 1414 on the left
    A1: sorted list
    8,11,14,19,22,27,35,418, 11, 14, 19, 22, 27, 35, 41
    (b)
    The list is instead sorted using a bubble sort. In each pass, adjacent items are compared from the left and swapped if they are in the wrong order.
    (i) Write down the list after the first pass.

    (ii) Write down the list after the second pass.

    (iii) The list is in order after the fifth pass. Explain why a sixth pass is still needed.
    [6 marks]
    Show the mark scheme

    Mark scheme

    M1: (i) first four items 14,27,8,2214, 27, 8, 22 correct
    A1: (i)
    14,27,8,22,35,11,19,4114, 27, 8, 22, 35, 11, 19, 41
    M1: (ii) second pass applied to their list from (i)

    A1: (ii)
    14,8,22,27,11,19,35,4114, 8, 22, 27, 11, 19, 35, 41
    B1: (iii) the sixth pass makes no swaps

    B1: (iii) only a pass with no swaps shows that the list is sorted

    Total for question 4: 12 marks

End of questions

Subtopic tests