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.