The Quick Sort Algorithm

It's only fair to share...Share on FacebookTweet about this on TwitterPin on PinterestShare on Google+Share on RedditEmail this to someone

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.

Comments are closed.