CS计算机代考程序代写 python javascript Java android c++ Excel algorithm COMP20007 Design of Algorithms

COMP20007 Design of Algorithms
Sorting – Part 2
Daniel Beck
Lecture 12
Semester 1, 2020
1

Mergesort
function Mergesort(A[0..n − 1]) if n > 1 then
B[0..�n/2� − 1] ← A[0..�n/2� − 1] C [0..�n/2� − 1] ← A[�n/2�..n − 1] Mergesort(B[0..�n/2� − 1]) Mergesort(C [0..�n/2� − 1]) Merge(B,C,A)
2

Mergesort – Merge function
function Merge(B [0..p − 1], C [0..q − 1], A[0..p + q − 1]) i ← 0; j ← 0; k ← 0
while i < p and j < q do if B[i] ≤ C[j] then A[k ] ← B [i ]; i ← i + 1 else A[k ] ← C [j ]; j ← j + 1 k←k+1 if i ==p then A[k..p + q − 1] ← C[j..q − 1] else A[k..p + q − 1] ← B[i..p − 1] 3 Mergesort - Properties Divide-and-Conquer algorithm 4 Mergesort - Properties Divide-and-Conquer algorithm • In contrast with decrease-and-conquer algorithms, such as Insertion Sort. 4 Mergesort - Properties Divide-and-Conquer algorithm • In contrast with decrease-and-conquer algorithms, such as Insertion Sort. Questions! 4 Mergesort - Properties Divide-and-Conquer algorithm • In contrast with decrease-and-conquer algorithms, such as Insertion Sort. Questions! • In-place? (or does it require extra memory?) • Stable? 4 Mergesort - Properties • In-place? 5 Mergesort - Properties • In-place? No. (requires O(n) auxiliary array + O(log n) stack space for recursion) • Stable? 5 Mergesort - Properties • In-place? No. (requires O(n) auxiliary array + O(log n) stack space for recursion) • Stable? Yes! (Merge keeps relative order with additional bookkeeping) 5 Mergesort - Complexity • Worst case? • Best case? • Average case? 6 Mergesort function Mergesort(A[0..n − 1]) if n > 1 then
B[0..�n/2� − 1] ← A[0..�n/2� − 1] C [0..�n/2� − 1] ← A[�n/2�..n − 1] Mergesort(B[0..�n/2� − 1]) Mergesort(C [0..�n/2� − 1]) Merge(B,C,A)
7

Mergesort – Complexity
8

Mergesort – In Practice
• Guaranteed Θ(n log n) complexity
• Highly parallelisable
• Multiway Mergesort: excellent for secondary memory
• Used in JavaScript (Mozilla)
• Basis for hybrid algorithms (TimSort: Python, Android)
Take-home message: Mergesort is an excellent choice if stability is required and the extra memory cost is
low.
9

Quicksort
function Quicksort(A[l ..r ]) if l < r then s ← Partition(A[l..r]) Quicksort(A[l..s − 1]) Quicksort(A[s + 1..r ]) � Starts with A[0..n − 1] 10 Quicksort - Lomuto partitioning function LomutoPartition(A[l..r]) p ← A[l] s←l for i ← l + 1 to r do if A[i] < p then s←s+1 Swap(A[s ], A[i ]) Swap(A[l ], A[s ]) return s 11 Quicksort - Properties Divide-and-Conquer algorithm 12 Quicksort - Properties Divide-and-Conquer algorithm Questions! 12 Quicksort - Properties Divide-and-Conquer algorithm Questions! • In-place? • Stable? 12 Quicksort - Properties • In-place? 13 Quicksort - Properties • In-place? Yes, buy still requires O(log n) memory for the stack. 13 Quicksort - Properties • In-place? Yes, buy still requires O(log n) memory for the stack. • Stable? 13 Quicksort - Properties • In-place? Yes, buy still requires O(log n) memory for the stack. • Stable? No (non-local swaps) 13 Quicksort - Partitioning • Lomuto partitioning can be used but not the best in pratice. 14 Quicksort - Partitioning • Lomuto partitioning can be used but not the best in pratice. • Instead, practical implementations use Hoare partitioning (proposed by the inventor of Quicksort). 14 Quicksort - Partitioning • Lomuto partitioning can be used but not the best in pratice. • Instead, practical implementations use Hoare partitioning (proposed by the inventor of Quicksort). • How does it work? Let’s go back to my games first... 14 Quicksort - Hoare partitioning function HoarePartition(A[l..r]) p ← A[l] i ← l; j ← r + 1 repeat repeat i ← i + 1 until A[i] ≥ p repeat j ← j − 1 until A[j] ≤ p Swap(A[i ], A[j ]) until i ≥ j Swap(A[i ], A[j ]) Swap(A[l ], A[j ]) return j 15 Quicksort - Complexity • Worst case? • Best case? • Average case? 16 Quicksort - Complexity • Worst case? • Best case? • Average case? Warning: not trivial, but give it a go. 😉 16 Quicksort - Complexity 17 Quicksort - Complexity 18 Quicksort - In practice • Used in C (qsort) • Basis for C++ sort (Introsort) • Fastest sorting algorithm in most cases 19 Quicksort - In practice • Used in C (qsort) • Basis for C++ sort (Introsort) • Fastest sorting algorithm in most cases Take-home message: Quicksort is the algorithm of choice when speed matters and stability is not required. 19 Summary so far Selection Sort: Slow, but only O(n) key exchanges. 20 Summary so far Selection Sort: Slow, but only O(n) key exchanges. Insertion Sort: Very good for small arrays and when data is expected to be “almost sorted”. 20 Summary so far Selection Sort: Slow, but only O(n) key exchanges. Insertion Sort: Very good for small arrays and when data is expected to be “almost sorted”. Mergesort: Better for mid-size arrays and when stability is required. 20 Summary so far Selection Sort: Slow, but only O(n) key exchanges. Insertion Sort: Very good for small arrays and when data is expected to be “almost sorted”. Mergesort: Better for mid-size arrays and when stability is required. Quicksort: Usually the best choice for large arrays, with excellent empirical performance and only O(log n) memory cost. 20 Summary so far Selection Sort: Slow, but only O(n) key exchanges. Insertion Sort: Very good for small arrays and when data is expected to be “almost sorted”. Mergesort: Better for mid-size arrays and when stability is required. Quicksort: Usually the best choice for large arrays, with excellent empirical performance and only O(log n) memory cost. Next lecture: Heapsort 20