Page 262 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 12: Sorting

Notes
Example: Sort {1, 12, 5, 26, 7, 14, 3, 7, 2} using quicksort.

1 12 5 26 7 14 3 7 2 16 > 5, swap

1 12 5 26 7 14 3 7 2 pivot value = 7

i pivot value j
1 12 5 26 7 14 3 7 2 12 > 7 > 2, swap 12 and 2
i j
1 2 5 26 7 14 3 7 12 26 > 7 > 7, swap 26 and 7

i j
1 2 5 7 7 14 3 7 12 7 > 7 > 3, swap 7 and 3

i j
1 2 5 7 3 14 7 26 12 i > j > 3, stop partition
i j
1 2 5 7 14 7 26 12 run quick sort recursively
. . .

1 2 3 5 7 7 12 14 26 sorted

Notice, that we show here only the fi rst recursion step, in order not to make example too long.
But, in fact, {1, 2, 5, 7, 3} and {14, 7, 26, 12} are sorted then recursively.
Why does it work?

On the partition step algorithm divides the array into two parts and every element a from the
left part is less or equal than every element b from the right part. Also a and b satisfy a ≤ pivot ≤
b inequality. After completion of the recursion calls both of the parts become sorted and, taking
into account arguments stated above, the whole array is sorted.

Example: Consider the following list to be sorted in ascending order. ‘ADD YOUR MAN’.
(Ignore blanks) N = 10

0 1 2 3 4 5 6 7 8 9
A[] = A D D Y O U R M A N

Quicksort (A, 0, 9)
1. 9 > 0
2. V = [ 9] = ‘N’
L = 1-1 = 0
R = I= 9

4. A[ 3] = ‘Y’ > V; There fore, L = 3
5. A [8] = ‘A’ > V; There fore, R = 8

LOVELY PROFESSIONAL UNIVERSITY 257