Quicksort

Overview

How quicksort works, pivot in quicksort and average and worst case time complexity of quicksort.

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 quicksort works.

   Model answer

   Quicksort chooses a pivot and partitions the list into items below the pivot and items above it. The two sublists are then sorted by the same method until each holds one item.

2. 2

   What is a pivot in quicksort?

   Model answer

   The pivot is the item the list is partitioned around. Items smaller than the pivot go to one side and larger items to the other.

3. 3

   After the first partition, what is known about the position of the pivot?

   Model answer

   The pivot is already in its final sorted position. Later steps never move that item again.

4. 4

   Quicksort is applied to 7, 2, 9, 4, 1, 8, 5 using the first item as pivot. State the two sublists after the first partition.

   Model answer

   The lower sublist holds 2, 4, 1 and 5. The upper sublist holds 9 and 8, with the pivot 7 fixed between them.

5. 5

   Give the fully sorted result of quicksort applied to 7, 2, 9, 4, 1, 8, 5.

   Model answer

   The sorted list reads 1, 2, 4, 5, 7, 8, 9. Quicksort reaches it by sorting each sublist by the same method.

6. 6

   Why is quicksort described as a divide and conquer algorithm?

   Model answer

   The problem is divided into two smaller sorting problems at every step. Each smaller problem is solved by the same algorithm.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.