## The Quick Sort Algorithm

The mid-point of a list has position [½(N+1)]

where [x] is the smallest integer greater than or equal to x

e.g. for 3, 6, 7, 11, 15 [½ (5+1)] = [3] = 3 mid-point = 7

for A, C, Y, B, D, R [½ (6+1)] = [3½] = 4 mid-point = B

Step 1

Locate the pivot element (use the element at the mid-point)

Step 2

Split the list into two sub-lists.

Sublist L1 contains those numbers less than or equal to the pivot and are written to the left of the pivot.

Sublist L2 contains those numbers greater than the pivot element and are written to the right of the pivot.

Do not reorder the numbers in the sub-lists

Step 3

Repeat Step 2 on each sub-list and each successive sub-list

Step 4

Stop when each sub-list contains only one number. The list is now sorted!

Example

Use a quick-sort to arrange these numbers in numerical order

27 15 2 19 16 1

Mid-point = [½(6+1)] = [3½] = 4th number = 19

27 15 2 __19 __ 16 1

15 2 16 1 19 27

L1 L2

15 2 __16 __ 1 19 27

15 2 1 16 19 27

L1 L2

15 __2 __ 1 16 19 27

1 2 15 16 19 27 Stop

Example

Use a quick-sort to arrange these letters in alphabetical order.

Y T A B F S F L

Mid-point = [½(8 + 1)] = [4½] = 5th letter = F

The pivot point is underlined at each stage.

Y T A B __F __ S F L

A B F F Y T S L

A __B __ F F L __S __ Y T

A B F F L S T Y Stop

Example

Use a quick-sort to arrange these letters in numerical order.

16 21 15 3 12 9 27 6 18 17

Mid-point = [½(10 + 1)] = [5½] = 6th number = 9

The pivot point is underlined at each stage.

16 21 15 3 12 __9 __ 27 6 18 17

3 6 9 16 21 15 __12 __ 27 18 17

3 6 9 12 16 21 15 27 18 17

3 6 9 12 16 21 __15 __ 18 17 27

3 6 9 12 15 16 21 18 17 27

3 6 9 12 15 16 17 __18 __ 21 27

3 6 9 12 15 16 17 18 21 27 STOP

Common Errors

1) The choice of pivot must be constant. If you have an even number of items in a list, the middle number is not clear. If you choose the right-hand number the first time, you must continue to select the right-hand number each time you have a choice.

2) Do not be tempted to reorder the items in a sub-list.

3) Remember that it is the method that is being assessed and not the answer. So make sure enough working is being shown. The list should be rewritten each time a new sub-list is created.

4) Remember to indicate the stop step.