INN701 Lecture 3
Queensland University of Technology
CRICOS No. 00213J
CAB301 Algorithms and Complexity
Lecture 6 – Advanced sorting algorithms
Maolin Tang
School of Computer Science
Queensland University of Technology
CRICOS No. 00213J
a university for the worldreal R 2
Aims of this lecture
• In this lecture we examine three advanced sorting algorithms:
– Merge sort
– Quick sort
– Heap sort
CRICOS No. 00213J
a university for the worldreal R
References
• A. Levitin. Introduction to the Design and Analysis of Algorithms.
Addison-Wesley, third edition, 2012. Sections 5.1, 5.2 and 6.4
• T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein,
Introduction to Algorithms, third edition, 2009. Chapters 6 and 7.
3
CRICOS No. 00213J
a university for the worldreal R 4
Merge sort
• A divide-and-conquer algorithm, which works by recursively
breaking down a problem into two sub-problems of the same type,
until these become simple enough to be solved directly. The
solutions to the sub-problems are then combined to give a solution
to the original problem.
• It consists of two main procedures: Mergesort and Merge.
– Mergesort recursively breakdowns an (sub)array into two smaller
subarrays.
– Merge combines two sorted subarrays to form one sorted (sub)array.
CRICOS No. 00213J
a university for the worldreal R
Merge
5
CRICOS No. 00213J
a university for the worldreal R 6
CRICOS No. 00213J
a university for the worldreal R 7
CRICOS No. 00213J
a university for the worldreal R 8
ALGORITHM Merge(A[i…j], m)
// Merges sorted subarrays A[i…m] and A[m + 1…j] into a single
// sorted subarray A[i…j], via temporary array T[i…j]
p ← i; q ← m + 1; r ← i
while p ≤ m and q ≤ j do
if A[p] ≤ A[q] // Copy item from first subarray
T[r] ← A[p]
p ← p + 1
else // Copy item from second subarray
T[r] ← A[q]
q ← q + 1
r ← r + 1
if p ≤ m then // Copy remainder of first subarray, if any
T[r…j] ← A[p…m]
if q ≤ j then // Copy remainder of second subarray, if any
T[r…j] ← A[q…j]
A[i…j] ← T[i…j] // Copy temporary array
CRICOS No. 00213J
a university for the worldreal R 9
Merge sort
• The following version of the algorithm passes array slices as in/out
parameters and allows assignment to array slices:
ALGORITHM Mergesort(A[i…j])
// Sorts (sub)array A into nondecreasing order, from position i
// to position j, inclusive
if i < j
m ← (i + j)/2
Mergesort(A[i…m])
Mergesort(A[m + 1…j])
Merge(A[i…j], m)
CRICOS No. 00213J
a university for the worldreal R 10
Mergesort(A[4…7])Mergesort(A[0…3])
Mergesort(A[0…1]) Mergesort(A[2…3])
Mergesort(A[0…0]) Mergesort(A[1…1])
Mergesort(A[0…7])
Merge(A[0…1], 0)
Merge(A[0…3], 1)
Merge(A[0…7], 3)
CRICOS No. 00213J
a university for the worldreal R 11
Efficiency of the merge sort algorithm
• Time efficiency
– In the worst case: Cworst(n) ∈ O(n log n), where n is the length of
the array
– In the average case: Cavg(n) ∈ O(n log n), where n is the length of
the array
• Space efficiency
– Need temporary space
• Stable
CRICOS No. 00213J
a university for the worldreal R
Quick sort
• A divide-and-conquer algorithm
• The algorithm consists of two main procedures Partition and
Quicksort
12
CRICOS No. 00213J
a university for the worldreal R
Partition
5 3 9 6 2 7 1 4 8 pivot = 5
i j
5 3 9 6 2 7 1 4 8 pivot = 5
i j
i j
5 3 4 6 2 7 1 9 8 pivot = 5
5 3 4 1 2 7 6 9 8 pivot = 5
j i
2 3 4 1 5 7 6 9 8
unsorted
pivot = 5
13
CRICOS No. 00213J
a university for the worldreal R 14
CRICOS No. 00213J
a university for the worldreal R
Quicksort
15
CRICOS No. 00213J
a university for the worldreal R
Quicksort
1 2 4 3 5 7 6 9 8
1 2 4 3 5 7 6 9 8
1 2 3 4 5 7 6 9 8
1 2 3 4 5 7 6 9 8
unsorted
pivot = 2
pivot = 1
pivot = 4
pivot = 3
16
CRICOS No. 00213J
a university for the worldreal R
Quicksort
1 2 3 4 5 6 7 9 8
unsorted
1 2 3 4 5 6 7 9 8
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
pivot = 7
pivot = 6
pivot = 9
pivot = 8
17
CRICOS No. 00213J
a university for the worldreal R 18
Efficiency of the quick sort algorithm
• Time efficiency
– In the worst case
Cworst(n) ∈ O(n2)
– In the average case
Cavg(n) ∈ O(n log n)
• Space efficiency
– No temporary storage needed
• Not stable
CRICOS No. 00213J
a university for the worldreal R
Heap sort
• A transform-and-conquer algorithm
• A transform-and-conquer algorithm is generally a two-stage
procedures.
– First, in the transformation stage, the problem’s instance is
modified to be, for one reason or another, more amenable to
solution;
– Then, in the conquer stage, it is solved.
19
CRICOS No. 00213J
a university for the worldreal R
Complete binary trees
• A complete binary tree of height h is a binary tree that is full down
to level h-1, with level h filled in from left to right.
– All nodes at level h-2 and above have two children each, and
– When a node at level h-1 has children, all nodes to its left at the
same level have two children each, and
– When a node at level h-1 has one child, it is a left child.
20
CRICOS No. 00213J
a university for the worldreal R
Complete binary trees
complete binary trees not a complete binary tree
21
CRICOS No. 00213J
a university for the worldreal R
Complete binary trees
• A complete binary tree can be conveniently implemented in an array:
– The root is stored at index 0;
– If a node is stored at index i in the array
• The left child of the node is stored at index 2*i+1, if it exists;
• The right child of the node is stored at index 2*i+2, if it exists;
• The parent of the node is stored at index (i-1)/2, if it is not the
root.
22
CRICOS No. 00213J
a university for the worldreal R
Complete binary trees
6
3 5
9 2 10
6 102953
0 1 2 3 4 5
23
CRICOS No. 00213J
a university for the worldreal R
Heaps
• A heap is a complete binary tree
– that is empty, or
– whose root contains a search key that is greater than or equals to
the search key in each of its children, and has heaps as its
subtrees.
• Such a heap is also known a maximum heap.
24
CRICOS No. 00213J
a university for the worldreal R
Heaps
a heap not a heap
10
523
69
10
5113
69
10
523
69
not a heap
25
CRICOS No. 00213J
a university for the worldreal R
Bottom Up
10 523 69
10
9
63 2 5
11 11
10 523 69109
63 2 5
11
11
10 52369
10
9 6
3 2 5 11
11– Shift the new node up
to its correct position
26
CRICOS No. 00213J
a university for the worldreal R
Maximum Key Deletion
1. Exchange the root’s key with the last key K of the heap;
2. Decrease the heap’s size by 1;
3. “Heapify” the complete binary tree.
27
CRICOS No. 00213J
a university for the worldreal R
Maximum Key Deletion
10 523 69109
63 2 5
11
11
10 5236 9109
6
3 2 5
28
CRICOS No. 00213J
a university for the worldreal R
Maximum Key Deletion
10 5236 9109
6
3 2 5
6 52310 969
10
3 2 5
– Shift the new root down to its correct position in the heap
29
CRICOS No. 00213J
a university for the worldreal R
HeapBottomUp
• Convert a complete binary tree into a heap
30
CRICOS No. 00213J
a university for the worldreal R
HeapBottomUp
6 102953
6
3 5
9 2 10
6 529103
6
3 10
9 2 5
6 523109
6
9 10
3 2 5
10 52369
10
9 6
3 2 5
31
CRICOS No. 00213J
a university for the worldreal R
Heapsort algorithm
ALGORITHM Heapsort(A[0…n-1])
// Sorts array A into nondecreasing order
consider A as a complete binary tree and convert it into a heap using the
HeapBottomUp procedure
for v ← 0 to n-2 do
Use the MaximumKeyDeletion procedure to delete the root of the heap
32
CRICOS No. 00213J
a university for the worldreal R
Heapsort
6 102953
6
3 5
9 2 10
The initial array and its corresponding complete binary tree
33
CRICOS No. 00213J
a university for the worldreal R
Heapsort
After making the complete binary tree a heap
10 52369
10
9 6
3 2 5
– Use the HeapBottomUp procedure to convert the
corresponding complete binary tree of the array into a heap
34
CRICOS No. 00213J
a university for the worldreal R
Heapsort
5 102369
5
9 6
3 2
complete binary tree sorted
9 102365
9
5 6
3 2
heap sorted
– Repeat the Maximum Key Deletion procedure until the heap
contains only one item
35
CRICOS No. 00213J
a university for the worldreal R
Heapsort
2 109365
2
5 6
3
complete binary tree sorted
6 109325
6
5 2
3
heap sorted
36
CRICOS No. 00213J
a university for the worldreal R
Heapsort
3 109625
3
5 2
complete binary tree sorted
5 109623
5
3 2
heap sorted
37
CRICOS No. 00213J
a university for the worldreal R
Heapsort
2 109653
2
3
sortedcomplete binary tree
3 109652
3
2
sortedheap
38
CRICOS No. 00213J
a university for the worldreal R
Heapsort
2 109653
2sorted
complete
binary tree
2 109653
sorted
39
CRICOS No. 00213J
a university for the worldreal R 40
Efficiency of the heap sort algorithm
• Time efficiency
– In the worst case: Cworst(n) ∈ O(n log n)
– In the average case: Cavg(n) ∈ O(n log n)
• Space efficiency
– No temporary storage needed
• Not stable
CAB301 Algorithms and Complexity��Lecture 6 – Advanced sorting algorithms
Aims of this lecture
References
Merge sort
Merge
Slide Number 6
Slide Number 7
Slide Number 8
Merge sort
Slide Number 10
Efficiency of the merge sort algorithm
Quick sort
Partition
Slide Number 14
Quicksort
Quicksort
Quicksort
Efficiency of the quick sort algorithm
Heap sort
Complete binary trees
Complete binary trees
Complete binary trees
Complete binary trees
Heaps
Heaps
Bottom Up
Maximum Key Deletion
Maximum Key Deletion
Maximum Key Deletion
HeapBottomUp
HeapBottomUp
Heapsort algorithm
Heapsort
Heapsort
Heapsort
Heapsort
Heapsort
Heapsort
Heapsort
Efficiency of the heap sort algorithm