CS计算机代考程序代写 algorithm INN701 Lecture 3

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