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