DATA
STRUCTURES
MAHESH GOYANI
MAHATMA GANDHI INSTITUE OF TECHNICAL EDUCATION & RESEARCH CENTER
mgoyani@rediffmail.com
(C) GOYANI MAHESH 1
QUICK
SORT
(C) GOYANI MAHESH 2
Quick Sort
Divide:
Pick any element p as the pivot, e.g, the first element
Partition the remaining elements into
FirstPart, which contains all elements < p
SecondPart, which contains all elements ≥ p
Recursively sort the FirstPart and SecondPart
Combine: no work is necessary since sorting
is done in place
(C) GOYANI MAHESH 3
Quick Sort
A: p
pivot Partition
FirstPart SecondPart
x<p p p≤x
Recursive call
Sorted Sorted
FirstPart SecondPart
x<p p p≤x
Sorted
(C) GOYANI MAHESH 4
Quick Sort
88 52
14
31
25 98 30
62 23
79
Divide and Conquer
(C) GOYANI MAHESH 5
Quick Sort
Partition set into two using
randomly chosen pivot
88 52
14
31
25 98 30
62 23
79
14 88
98
31 30 23 ≤ 52 ≤ 62
25 79
(C) GOYANI MAHESH 6
Quick Sort
14 88
98
31 30 23 ≤ 52 ≤ 62
25 79
sort the first half. sort the second half.
14,23,25,30,31 62,79,98,88
(C) GOYANI MAHESH 7
Quick Sort
14,23,25,30,31
52
62,79,88,98
Glue pieces together.
(No real work)
14,23,25,30,31,52,62,79,88,98
(C) GOYANI MAHESH 8
Quick-Sort
Quick-sort is a randomized
sorting algorithm based on x
the divide-and-conquer
paradigm:
– Divide: pick a random
element x (called pivot) and
x
partition S into
L elements less than x L E G
E elements equal x
G elements greater than x
– Recur: sort L and G
– Conquer: join L, E and G x
(C) GOYANI MAHESH 9
Quick Sort
Let pivot be the first
88 52 element in the list?
14
31
25 98 30
62 23
79
14 88
98
30 ≤ 31 ≤ 62
25 23 52 79
(C) GOYANI MAHESH 10
Quick Sort
14,23,25,30,31,52,62,79,88,98
≤ 14 ≤ 23,25,30,31,52,62,79,88,98
If the list is already sorted,
then the slit is worst case unbalanced.
(C) GOYANI MAHESH 11
Partition Example
A: 4 8 6 3 5 1 7 2
(C) GOYANI MAHESH 12
Partition Example
i=0
A: 4 8 6 3 5 1 7 2
j=1
(C) GOYANI MAHESH 13
Partition Example
i=0
A: 4 8 6 3 5 1 7 2
j=1
(C) GOYANI MAHESH 14
Partition Example
i=0
A: 4 8 6 3 5 1 7 2
j=2
(C) GOYANI MAHESH 15
Partition Example
i=0i=1
A: 4 8
3 6 3
8 5 1 7 2
j=3
(C) GOYANI MAHESH 16
Partition Example
i=1
A: 4 3 6 8 5 1 7 2
j=4
(C) GOYANI MAHESH 17
Partition Example
i=1
A: 4 3 6 8 5 1 7 2
j=5
(C) GOYANI MAHESH 18
Partition Example
i=2
A: 4 3 1
6 8 5 6
1 7 2
j=5
(C) GOYANI MAHESH 19
Partition Example
i=2
A: 4 3 1 8 5 6 7 2
j=6
(C) GOYANI MAHESH 20
Partition Example
i=2i=3
A: 4 3 1 2
8 5 6 7 8
2
j=7
(C) GOYANI MAHESH 21
Partition Example
i=3
A: 4 3 1 2 5 6 7 8
j=8
(C) GOYANI MAHESH 22
Partition Example
i=3
A: 24 3 1 4
2 5 6 7 8
(C) GOYANI MAHESH 23
Partition Example
pivot in
correct position
A: 2 3 1 4 5 6 7 8
x<4 4≤x
(C) GOYANI MAHESH 24
Quick Sort
Picking the pivot:
Median of three
Find the first, middle and last element in the array. Use the
median of the three as the pivot.
(C) GOYANI MAHESH 25
Partitioning the list:
1. Swap the pivot element with the last element.
8 1 4 9 6 3 5 2 7 0
8 1 4 9 0 3 5 2 7 6
2. Set i to the first element and j to the next to last element.
8 1 4 9 0 3 5 2 7 6
i j
(C) GOYANI MAHESH 26
Partitioning the list:
3. Move i to the right until it refers to an element that is larger than
the value at the pivot.
8 1 4 9 0 3 5 2 7 6
i j
4. Move j to the left until it refers to an element that is smaller than
the value at the pivot.
8 1 4 9 0 3 5 2 7 6
i j
(C) GOYANI MAHESH 27
Partitioning the list:
5. If i is to the left of j, swap the elements at positions i and j.
8 1 4 9 0 3 5 2 7 6
i j
2 1 4 9 0 3 5 8 7 6
i j
(C) GOYANI MAHESH 28
Partitioning the list:
6. Continue the process until i and j meet or i surpasses j.
2 1 4 9 0 3 5 8 7 6
i j
2 1 4 5 0 3 9 8 7 6
j i
7. Swap the pivot element and the element at position i.
2 1 4 5 0 3 6 8 7 9
(C) GOYANI MAHESH 29
Complexity
cn cn
cn/2 cn/2 cn
h = lg n cn/4 cn/4 cn/4 cn/4 cn
…
…
(1) #leaves = n (n)
Total(n lg n)
O( n log2n ) average case
O( n2 ) worst case
(C) GOYANI MAHESH 30
