Sorting and searching algorithms

Sorting and searching algorithms

Spec 1.2 · Edexcel International A Level Maths: Revision notes

Studying this course? Keep your progress in one place.

Key facts

  • A bubble sort compares neighbouring items and swaps them if they are the wrong way round; stop after a pass with no swaps.
  • A quick sort takes the middle item as the pivot, splits the rest into smaller and larger, then repeats on each sub-list.
  • A binary search needs an ordered list: compare with the middle item and discard the half that cannot contain the target.
  • The middle of NN items is position N+12\frac{N+1}{2} (odd NN) or N+22\frac{N+2}{2} (even NN).
  • Always show each pass, pivot or sub-list, and state the result in words.

Bubble sort

A bubble sort compares neighbouring items and swaps those in the wrong order, pass after pass, until a pass makes no swaps.

A bubble sort puts a list in order by repeated passes. In each pass, compare the first two items and swap them if they are in the wrong order, then the second and third, and so on to the end.

After pass 1 the largest item is at the end. After pass 2 the second largest is in place, so each pass can stop one place earlier.

Stop when a whole pass makes no swaps.

  1. 1

    Start

    15, 8, 23, 4, 16, 9

  2. 2

    Pass 1

    8, 15, 4, 16, 9, 23 (4 swaps)

  3. 3

    Pass 2

    8, 4, 15, 9, 16, 23 (2 swaps)

  4. 4

    Pass 3

    4, 8, 9, 15, 16, 23 (2 swaps)

  5. 5

    Pass 4

    No swaps, so the list is sorted

A bubble sort into ascending order

Worked example

Use a bubble sort to put 15, 8, 23, 4, 16, 9 into ascending order.

When does a bubble sort stop?

The middle item

The middle item 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.

Quick sort and binary search both need the middle item.

  • N=9N=9 gives the 5th item.
  • N=6N=6 gives the 4th item.
  • N=10N=10 gives the 6th item.

Apply the rule to each new sub-list, renumbering from 1.

12345678910N=6: 4thN=9: 5thN=10: 6th
Middle item positions: N = 9 gives the 5th, N = 6 the 4th, N = 10 the 6th.
  • N oddposition N+12\dfrac{N+1}{2}
  • N evenposition N+22\dfrac{N+2}{2}

Which position is the middle of 8 items?

Quick sort

A quick sort picks the middle item as pivot, puts smaller items to its left and larger to its right, then repeats on each sub-list.

Quick sort is a divide-and-conquer sort.

  1. Choose the middle item as the pivot.
  2. Write items smaller than the pivot to its left and larger items to its right, keeping their original order within each side.
  3. The pivot is now in its final position.
  4. Repeat on each sub-list, left first, until every sub-list has at most one item.
  1. 1

    Choose the pivot

    the middle item of the list

  2. 2

    Split

    smaller items left, larger right, order kept

  3. 3

    Fix the pivot

    it is now in its final place

  4. 4

    Repeat

    on each sub-list, left first

One round of quick sort

Worked example

Use quick sort on 27, 14, 35, 8, 22, 41, 11, 19.

After the first pivot, what is true of the pivot?

Choosing between methods

Bubble sort is simple but needs many passes on long lists; quick sort usually needs far fewer comparisons; a binary search halves an ordered list each time.

A binary search needs at most about log⁡2N\log_2 N comparisons, because a list of NN items is halved each time. This is far fewer than checking every item in turn.

Whichever method you use, show each pass or sub-list clearly, give the final result and state any conclusion (found or not found) in words.

5101520253051015202530xyCheck every itemBinary search
Worst-case comparisons for a list of x items: checking every item (x) against a binary search (log₂ x).

Bubble sort

  • Swaps neighbours
  • Many passes for long lists

Quick sort

  • Splits around a pivot
  • Usually far fewer comparisons

Binary search

  • Needs an ordered list
  • Halves the list each time
Comparing the three methods

Which method finds an item in an ordered list fastest?

Try an exam question

A list of numbers is 19, 7, 23, 12, 5, 16. (a) Perform one pass of a bubble sort, writing down the list after the pass. (b) Use the quick sort algorithm, with the middle item as pivot, to put the list into ascending order, showing the first pivot and its two sub-lists.

[4 marks]

That's the notes covered.

Carry on to the next subtopic.

Try a question

What is the list after the first pass?

1 mark, marked against the mark scheme

Revision notes