Why a variety of sorting algorithms is needed

Overview

Recursive and a non-recursive sorting algorithm, one recursive and one non-recursive sorting algorithm and in-place 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

   Why does more than one sorting algorithm exist?

   Model answer

   Each algorithm is fastest in different circumstances, so none is best for every situation. The choice depends on the size of the data, how nearly sorted it is and the memory available.

2. 2

   Give two properties of a data set that influence which sort should be used.

   Model answer

   The number of items and how nearly sorted they already are both matter. The amount of spare memory available is a third factor.

3. 3

   Which sorting algorithm suits a small list that is already nearly in order?

   Model answer

   Insertion sort suits nearly sorted data because few items have to move. The algorithm approaches O(n) on such a list.

4. 4

   Which sorting algorithm is generally chosen for a large unordered list held in memory?

   Model answer

   Quicksort is generally chosen because its average performance is O(n log n). The algorithm also sorts in place and needs little extra memory.

5. 5

   Distinguish between a recursive and a non-recursive sorting algorithm.

   Model answer

   A recursive sort calls itself on smaller parts of the data, as quicksort does. A non-recursive sort uses loops only, as bubble sort and insertion sort do.

6. 6

   Name one recursive and one non-recursive sorting algorithm.

   Model answer

   Quicksort is a recursive sorting algorithm. Bubble sort is a non-recursive sorting algorithm.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.