Standard algorithms: sorting, searching and compression

Overview

How a bubble sort puts a list into order, how an insertion sort puts a list into order and one advantage of an insertion sort over a bubble sort.

What you need to know

Answer each one before you reveal it.

Questions from this subtopic

Each one with the model answer underneath.

1. 1

   Describe how a bubble sort puts a list into order.

   Model answer

   A bubble sort compares each adjacent pair in turn and swaps them if they are the wrong way round, repeating these passes until a whole pass makes no swap, with the largest value reaching the end after the first pass.

2. 2

   How does a bubble sort detect that the list is already in order?

   Model answer

   It records whether any swap was made during a pass, and a pass that makes no swap at all shows every adjacent pair is in order so the sort can stop.

3. 3

   State the number of comparisons made by the first pass of a bubble sort on a list of 10 items.

   Model answer

   The first pass makes 9 comparisons, because it compares each of the 10 items with the one after it.

4. 4

   Describe how an insertion sort puts a list into order.

   Model answer

   An insertion sort takes each item in turn from the unsorted part and moves it back past every larger item until it sits in its correct place among those already sorted.

5. 5

   State one advantage of an insertion sort over a bubble sort.

   Model answer

   An insertion sort does far less work on a list that is already nearly in order, because each item usually needs no movement at all.

6. 6

   Describe how a linear search finds a value.

   Model answer

   A linear search examines each item from the beginning in turn, comparing it with the value wanted, and stops when it finds a match or reaches the end of the list.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.