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

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

Insertion Sort
function InsertionSort(A[0..n − 1]) for i ← 1 to n − 1 do
j←i−1
while j ≥ 0 and A[j + 1] < A[j] do SWAP(A[j + 1], A[j ]) j←j−1 2 Insertion Sort function InsertionSort(A[0..n − 1]) for i ← 1 to n − 1 do j←i−1 while j ≥ 0 and A[j + 1] < A[j] do SWAP(A[j + 1], A[j ]) j←j−1 • Decrease-And-Conquer algorithm. 2 Insertion Sort function InsertionSort(A[0..n − 1]) for i ← 1 to n − 1 do j←i−1 while j ≥ 0 and A[j + 1] < A[j] do SWAP(A[j + 1], A[j ]) j←j−1 • Decrease-And-Conquer algorithm. • The idea behind Insertion Sort is recursive, but the code given here, using iteration, is preferable to the recursive version. 2 Insertion Sort - Properties Questions! 3 Insertion Sort - Properties Questions! • In-place? (does it require extra memory?) 3 Insertion Sort - Properties Questions! • In-place? (does it require extra memory?) • Stable? (preserves original order of inputs?) 3 Insertion Sort - Properties Questions! • In-place? (does it require extra memory?) • Stable? (preserves original order of inputs?) function InsertionSort(A[0..n − 1]) for i ← 1 to n − 1 do j←i−1 while j ≥ 0 and A[j + 1] < A[j] do SWAP(A[j + 1], A[j ]) j←j−1 3 Insertion Sort - Properties function InsertionSort(A[0..n − 1]) for i ← 1 to n − 1 do j←i−1 while j ≥ 0 and A[j + 1] < A[j] do SWAP(A[j + 1], A[j ]) j←j−1 4 Insertion Sort - Properties function InsertionSort(A[0..n − 1]) for i ← 1 to n − 1 do j←i−1 while j ≥ 0 and A[j + 1] < A[j] do SWAP(A[j + 1], A[j ]) j←j−1 • In-place? 4 Insertion Sort - Properties function InsertionSort(A[0..n − 1]) for i ← 1 to n − 1 do j←i−1 while j ≥ 0 and A[j + 1] < A[j] do SWAP(A[j + 1], A[j ]) j←j−1 • In-place? Yes! (may need additional O(1) memory) 4 Insertion Sort - Properties function InsertionSort(A[0..n − 1]) for i ← 1 to n − 1 do j←i−1 while j ≥ 0 and A[j + 1] < A[j] do SWAP(A[j + 1], A[j ]) j←j−1 • In-place? Yes! (may need additional O(1) memory) • Stable? 4 Insertion Sort - Properties function InsertionSort(A[0..n − 1]) for i ← 1 to n − 1 do j←i−1 while j ≥ 0 and A[j + 1] < A[j] do SWAP(A[j + 1], A[j ]) j←j−1 • In-place? Yes! (may need additional O(1) memory) • Stable? Yes! (local, adjacent swaps ensure stability) 4 Insertion Sort - Properties function InsertionSort(A[0..n − 1]) for i ← 1 to n − 1 do j←i−1 while j ≥ 0 and A[j + 1] < A[j] do SWAP(A[j + 1], A[j ]) j←j−1 • In-place? Yes! (may need additional O(1) memory) • Stable? Yes! (local, adjacent swaps ensure stability) Compare with Selection Sort: • Also in-place. • Not stable. (swaps are not local) 4 Insertion Sort - Complexity function InsertionSort(A[0..n − 1]) for i ← 1 to n − 1 do j←i−1 while j ≥ 0 and A[j + 1] < A[j] do SWAP(A[j + 1], A[j ]) j←j−1 5 Insertion Sort - Complexity function InsertionSort(A[0..n − 1]) for i ← 1 to n − 1 do j←i−1 while j ≥ 0 and A[j + 1] < A[j] do SWAP(A[j + 1], A[j ]) j←j−1 • Worst case? • Best case? 5 Insertion Sort - Worst case function InsertionSort(A[0..n − 1]) for i ← 1 to n − 1 do j←i−1 while j ≥ 0 and A[j + 1] < A[j] do SWAP(A[j + 1], A[j ]) j←j−1 6 Insertion Sort - Best case function InsertionSort(A[0..n − 1]) for i ← 1 to n − 1 do j←i−1 while j ≥ 0 and A[j + 1] < A[j] do SWAP(A[j + 1], A[j ]) j←j−1 7 Insertion Sort - Average case function InsertionSort(A[0..n − 1]) for i ← 1 to n − 1 do j←i−1 while j ≥ 0 and A[j + 1] < A[j] do SWAP(A[j + 1], A[j ]) j←j−1 8 Insertion Sort - Complexity • Worst case: Θ(n2) • Best case: Θ(n) • Average case: Θ(n2) 9 Insertion Sort - Complexity • Worst case: Θ(n2) • Best case: Θ(n) • Average case: Θ(n2) Compare with Selection Sort, which is input-insensitve: best, average and worst case complexity is Θ(n2) 9 Insertion Sort - Complexity • Worst case: Θ(n2) • Best case: Θ(n) • Average case: Θ(n2) Compare with Selection Sort, which is input-insensitve: best, average and worst case complexity is Θ(n2) Insight In many cases, real-world data is already partially sorted. This makes Insertion Sort a powerful sorting algorithm in practice, particularly useful for small arrays (up to hundreds of elements). 9 Insertion Sort - A faster version function InsertionSort(A[0..n − 1]) for i ← 1 to n − 1 do v ← A[i] j←i−1 while j ≥ 0 and v < A[j] do A[j + 1] ← A[j] j←j−1 A[j + 1] ← v 10 Insertion Sort - A faster version function InsertionSort(A[0..n − 1]) for i ← 1 to n − 1 do v ← A[i] j←i−1 while j ≥ 0 and v < A[j] do A[j + 1] ← A[j] j←j−1 A[j + 1] ← v This is the version presented in the Levitin book. 10 Insertion Sort - Sentinels • Assume the domain is bounded from below. 11 Insertion Sort - Sentinels • Assume the domain is bounded from below. • There is a minimal element min. 11 Insertion Sort - Sentinels • Assume the domain is bounded from below. • There is a minimal element min. • Assume a free cell to the left of A[0] 11 Insertion Sort - Sentinels • Assume the domain is bounded from below. • There is a minimal element min. • Assume a free cell to the left of A[0] Insertion Sort can be made faster by using a min sentinel in that cell (A[−1]) and change the test from to just j ≥ 0 and v < A[j] v < A[j] 11 Insertion Sort - Sentinels • Assume the domain is bounded from below. • There is a minimal element min. • Assume a free cell to the left of A[0] Insertion Sort can be made faster by using a min sentinel in that cell (A[−1]) and change the test from to just j ≥ 0 and v < A[j] v < A[j] For this reason, extreme array cells (such as A[0] in C, and/or A[n + 1]) are sometimes left free deliberately, so that they can be used to hold sentinels; only A[1] to A[n] hold proper data. 11 Sorting - Practical Implementations • C - Quicksort (fastest) • C++ - Introsort (a variant of Quicksort) • Javascript/Mozilla: Mergesort (stable) • Python: Timsort (very roughly, a mix of Mergesort and Insertion Sort, stable) • Linux Kernel: Heapsort (low memory consumption, guaranteed Θ(nlogn) worst case performance: important for security reasons) 12