Comparing sorting algorithms

Overview

Four measures used to compare the efficiency of sorting algorithms, stable sort and pass through the data in a sorting algorithm.

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

   Name four measures used to compare the efficiency of sorting algorithms.

   Model answer

   They are the number of comparisons made, the number of exchanges made, the number of passes through the data and the extra storage space required.

2. 2

   Why is the number of exchanges a more telling measure than the number of comparisons when large records are sorted?

   Model answer

   Moving a whole record costs far more than comparing one key field, so the exchanges dominate the running time.

3. 3

   What does it mean to say that a sort is performed in place?

   Model answer

   An in-place sort rearranges the items within the storage they already occupy, needing only a constant amount of extra space whatever the size of the list.

4. 4

   State the number of comparisons a bubble sort makes on a list of ten items when no early exit is used.

   Model answer

   It makes 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 45 comparisons.

5. 5

   What effect does a swap flag have on the best-case running time of a bubble sort?

   Model answer

   A pass that makes no exchange shows the list is already in order and the sort ends there, so the best case falls to O(n).

6. 6

   Why is a selection sort attractive when writing to the storage medium is expensive?

   Model answer

   It makes at most one exchange per pass, so a list of n items costs at most n − 1 exchanges however disordered it is.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.