09.key
http://people.eng.unimelb.edu.au/tobym
@tobycmurray
toby.murray@unimelb.edu.au
DMD 8.17 (Level 8, Doug McDonell Bldg)
Toby Murray
COMP90038
Algorithms and Complexity
Lecture 9: Decrease-and-Conquer-by-a-Constant
(with thanks to Harald Søndergaard)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Decrease-and-Conquer-
by-a-Constant
• In this approach, the size of the problem is reduced
by some constant in each iteration of the
algorithm.
• A simple example is the following approach to
sorting: To sort an array of length n, just
1. sort the first n − 1 items, then
2. locate the cell that should hold the last item,
shift all elements to its right to the right, and
place the last element.
2
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Sorting n items
3
23 9 52 12 41 83 46A:
0 1 2 3 4 5 6
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Sorting n items
3
23 9 52 12 41 83 46A:
0 1 2 3 4 5 6
Sort first n-1 items
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Sorting n items
3
23 9 52 12 41 83 46A:
0 1 2 3 4 5 6
Sort first n-1 items
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Sorting n items
4
9 12 23 41 52 83 46A:
0 1 2 3 4 5 6
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Sorting n items
4
9 12 23 41 52 83 46A:
0 1 2 3 4 5 6
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
52
Sorting n items
5
9 12 23 41 83 46A:
0 1 2 3 4 5 6
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
52
Sorting n items
5
9 12 23 41 83 46A:
0 1 2 3 4 5 6
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
52
Sorting n items
5
9 12 23 41 83 46A:
0 1 2 3 4 5 6
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
52
Sorting n items
5
9 12 23 41 83 46A:
0 1 2 3 4 5 6
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
52
Sorting n items
5
9 12 23 41 8346A:
0 1 2 3 4 5 6
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Sorting n items
6
9 12 23 41 52 83 46A:
0 1 2 3 4 5 6
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Sorting n items
6
9 12 23 41 52 83 46A:
0 1 2 3 4 5 6
v: 46
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Sorting n items
6
9 12 23 41 52 83 46A:
0 1 2 3 4 5 6
v: 46
A[j]
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Sorting n items
7
9 12 23 41 52 83 83A:
0 1 2 3 4 5 6
v: 46
A[j]
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Sorting n items
8
9 12 23 41 52 83 83A:
0 1 2 3 4 5 6
v: 46
A[j]
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Sorting n items
9
9 12 23 41 52 52 83A:
0 1 2 3 4 5 6
v: 46
A[j]
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Sorting n items
10
9 12 23 41 52 52 83A:
0 1 2 3 4 5 6
v: 46
A[j]
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Sorting n items
11
9 12 23 41 46 52 83A:
0 1 2 3 4 5 6
v: 46
A[j]
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Sorting n items
12
9 12 23 41 46 52 83A:
0 1 2 3 4 5 6
v: 46
A[j]
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Insertion Sort
• Sorting an array A[0]..A[n − 1]:
• To sort A[0] .. A[i] first sort A[0] .. A[i-1], then insert A[i] in
its proper place
13
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
• The for loop is traversed n − 1 times. In the ith
round, the test v < A[j] is performed i times, in the
worst case.
• Hence the worst-case running time is
• What does input look like in the worst case?
Complexity of Insertion Sort
14
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
• The for loop is traversed n − 1 times. In the ith
round, the test v < A[j] is performed i times, in the
worst case.
• Hence the worst-case running time is
• What does input look like in the worst case?
Complexity of Insertion Sort
14
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
• The for loop is traversed n − 1 times. In the ith
round, the test v < A[j] is performed i times, in the
worst case.
• Hence the worst-case running time is
• What does input look like in the worst case?
Complexity of Insertion Sort
14
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
The Trick of Posting
a Sentinel
• If we are sorting elements from a domain that is bounded from
below, that is, there is a minimal element min, and the array A was
known to have a free cell to the left of A[0], then we could simplify
the test. Namely, we would place min (a sentinel) in that cell (A[−1])
and change the test from
j ≥ 0 and v < A[j]
to just
v < A[j]
• That will speed up insertion sort by a constant factor.
• 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.
15
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Posting a Sentinel
16
9 23 52 12 41 83 46A:
0 1 2 3 4 5 6
j ≥ 0 and v < A[j]Test required:
A[j]
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Posting a Sentinel
17
9 23 52 12 41 83 46
1 2 3 4 5 6 7
A: -1
0
v < A[j]Test required:
A[j]
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Properties of Insertion Sort
• Easy to understand and implement.
• Average-case and worst-case complexity both quadratic.
• However, linear for almost-sorted input.
• Some cleverer sorting algorithms perform almost-sorting
and then let insertion sort take over.
• Very good for small arrays (say, a couple of hundred
elements).
• In-place?
• Stable?
18
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Properties of Insertion Sort
• Easy to understand and implement.
• Average-case and worst-case complexity both quadratic.
• However, linear for almost-sorted input.
• Some cleverer sorting algorithms perform almost-sorting
and then let insertion sort take over.
• Very good for small arrays (say, a couple of hundred
elements).
• In-place?
• Stable?
18
yes
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Properties of Insertion Sort
• Easy to understand and implement.
• Average-case and worst-case complexity both quadratic.
• However, linear for almost-sorted input.
• Some cleverer sorting algorithms perform almost-sorting
and then let insertion sort take over.
• Very good for small arrays (say, a couple of hundred
elements).
• In-place?
• Stable?
18
yes
?
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Insertion Sort Stability
19
key: 4
val: ab
0 1 2 3
key: 3
val: bc
key: 4
val: de
key: 3
val: fg
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Insertion Sort Stability
19
key: 4
val: ab
0 1 2 3
key: 3
val: bc
key: 4
val: de
key: 3
val: fg
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Insertion Sort Stability
20
key: 3
val: bc
0 1 2 3
key: 4
val: ab
key: 4
val: de
key: 3
val: fg
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Insertion Sort Stability
20
key: 3
val: bc
0 1 2 3
key: 4
val: ab
key: 4
val: de
key: 3
val: fg
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Insertion Sort Stability
21
key: 3
val: bc
0 1 2 3
key: 4
val: ab
key: 4
val: de
key: 3
val: fg
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Insertion Sort Stability
21
key: 3
val: bc
0 1 2 3
key: 4
val: ab
key: 4
val: de
key: 3
val: fg Stable
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Properties of Insertion Sort
• Easy to understand and implement.
• Average-case and worst-case complexity both quadratic.
• However, linear for almost-sorted input.
• Some cleverer sorting algorithms perform almost-sorting
and then let insertion sort take over.
• Very good for small arrays (say, a couple of hundred
elements).
• In-place?
• Stable?
22
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Properties of Insertion Sort
• Easy to understand and implement.
• Average-case and worst-case complexity both quadratic.
• However, linear for almost-sorted input.
• Some cleverer sorting algorithms perform almost-sorting
and then let insertion sort take over.
• Very good for small arrays (say, a couple of hundred
elements).
• In-place?
• Stable?
22
yes
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Properties of Insertion Sort
• Easy to understand and implement.
• Average-case and worst-case complexity both quadratic.
• However, linear for almost-sorted input.
• Some cleverer sorting algorithms perform almost-sorting
and then let insertion sort take over.
• Very good for small arrays (say, a couple of hundred
elements).
• In-place?
• Stable?
22
yes
yes
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Shellsort: Motivation
23
9 8 7 6 5 4 3A:
0 1 2 3 4 5 6
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Shellsort: Motivation
23
9 8 7 6 5 4 3A:
0 1 2 3 4 5 6
8 9 7 6 5 4 3A:
0 1 2 3 4 5 6
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Shellsort: Motivation
23
9 8 7 6 5 4 3A:
0 1 2 3 4 5 6
8 9 7 6 5 4 3A:
0 1 2 3 4 5 6
7 8 9 6 5 4 3A:
0 1 2 3 4 5 6
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Shellsort: Motivation
23
9 8 7 6 5 4 3A:
0 1 2 3 4 5 6
8 9 7 6 5 4 3A:
0 1 2 3 4 5 6
7 8 9 6 5 4 3A:
0 1 2 3 4 5 6
It would be better if we could move the 9, 8, etc.
to the right faster
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Shellsort: Motivation
24
9 8 7 6 5 4 3A:
0 1 2 3 4 5 6
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Shellsort: Motivation
24
9 8 7 6 5 4 3A:
0 1 2 3 4 5 6
Sort the yellow entries
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Shellsort: Motivation
24
9 8 7 6 5 4 3A:
0 1 2 3 4 5 6
6 8 7 9 5 4 3A:
0 1 2 3 4 5 6
Sort the yellow entries
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Shellsort: Motivation
24
9 8 7 6 5 4 3A:
0 1 2 3 4 5 6
6 8 7 9 5 4 3A:
0 1 2 3 4 5 6
3 8 7 6 5 4 9A:
0 1 2 3 4 5 6
Sort the yellow entries
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Shellsort: Motivation
25
3 8 7 6 5 4 9A:
0 1 2 3 4 5 6
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Shellsort: Motivation
25
3 8 7 6 5 4 9A:
0 1 2 3 4 5 6
Sort the blue entries
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Shellsort: Motivation
25
3 8 7 6 5 4 9A:
0 1 2 3 4 5 6
3 5 7 6 8 4 9A:
0 1 2 3 4 5 6
Sort the blue entries
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Shellsort: Motivation
25
3 8 7 6 5 4 9A:
0 1 2 3 4 5 6
3 5 7 6 8 4 9A:
0 1 2 3 4 5 6
Sort the blue entries
Sort the pink entries
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Shellsort: Motivation
25
3 8 7 6 5 4 9A:
0 1 2 3 4 5 6
3 5 7 6 8 4 9A:
0 1 2 3 4 5 6
3 5 4 6 8 7 9A:
0 1 2 3 4 5 6
Sort the blue entries
Sort the pink entries
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Shellsort: Motivation
25
3 8 7 6 5 4 9A:
0 1 2 3 4 5 6
3 5 7 6 8 4 9A:
0 1 2 3 4 5 6
3 5 4 6 8 7 9A:
0 1 2 3 4 5 6
Sort the blue entries
Sort the pink entries
Notice how it
is now almost
sorted
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Shellsort: Motivation
25
3 8 7 6 5 4 9A:
0 1 2 3 4 5 6
3 5 7 6 8 4 9A:
0 1 2 3 4 5 6
3 5 4 6 8 7 9A:
0 1 2 3 4 5 6
Sort the blue entries
Sort the pink entries
Now do a final round of insertion sort over the entire array
Notice how it
is now almost
sorted
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Shellsort: Motivation
25
3 8 7 6 5 4 9A:
0 1 2 3 4 5 6
3 5 7 6 8 4 9A:
0 1 2 3 4 5 6
3 5 4 6 8 7 9A:
0 1 2 3 4 5 6
Sort the blue entries
Sort the pink entries
Now do a final round of insertion sort over the entire array
3 54 6 87 9A:
0 1 2 3 4 5 6
Notice how it
is now almost
sorted
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Shellsort
• We just did a shellsort for k=3
• In general:
• Think of the array as an interleaving of k lists
• Sort each list separately using insertion sort
• Then sort the resulting entire array using a final
pass of insertion sort
26
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Shellsort Passes and
Gap Sequences
• For large files, start with larger k and then repeat with
smaller ks
• It is common to start from somewhere in the sequence
1, 4, 13, 40, 121, 364, 1093, … and work backwards.
• what is the sequence?
• For example, for an array of size 20,000, start by 364-
sorting, then 121-sort, then 40-sort, and so on.
• Sequences with smaller gaps (a factor of about 2.3)
appear to work better, but nobody really understands
why.
27
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Properties of Shellsort
• Fewer comparisons than insertion sort. Known to
be worst-case for good gap sequences.
• Conjectured to be O(n1.25) but the algorithm is very
hard to analyse.
• Very good on medium-sized arrays (up to size
10,000 or so).
• In-place?
• Stable?
28
O(n n)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Properties of Shellsort
• Fewer comparisons than insertion sort. Known to
be worst-case for good gap sequences.
• Conjectured to be O(n1.25) but the algorithm is very
hard to analyse.
• Very good on medium-sized arrays (up to size
10,000 or so).
• In-place?
• Stable?
28
O(n n)
yes
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Properties of Shellsort
• Fewer comparisons than insertion sort. Known to
be worst-case for good gap sequences.
• Conjectured to be O(n1.25) but the algorithm is very
hard to analyse.
• Very good on medium-sized arrays (up to size
10,000 or so).
• In-place?
• Stable?
28
O(n n)
yes
?
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Shellsort: Stability
29
1 7 4 6 4 8 9A:
0 1 2 3 4 5 6
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Shellsort: Stability
29
1 7 4 6 4 8 9A:
0 1 2 3 4 5 6
after sorting
the blues
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Shellsort: Stability
29
1 7 4 6 4 8 9A:
0 1 2 3 4 5 6
1 4 4 6 7 8 9A:
0 1 2 3 4 5 6
after sorting
the blues
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Shellsort: Stability
29
1 7 4 6 4 8 9A:
0 1 2 3 4 5 6
1 4 4 6 7 8 9A:
0 1 2 3 4 5 6
after sorting
the blues
relative order of the two 4s has changed!
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Properties of Shellsort
• Fewer comparisons than insertion sort. Known to
be worst-case for good gap sequences.
• Conjectured to be O(n1.25) but the algorithm is very
hard to analyse.
• Very good on medium-sized arrays (up to size
10,000 or so).
• In-place?
• Stable?
30
O(n n)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Properties of Shellsort
• Fewer comparisons than insertion sort. Known to
be worst-case for good gap sequences.
• Conjectured to be O(n1.25) but the algorithm is very
hard to analyse.
• Very good on medium-sized arrays (up to size
10,000 or so).
• In-place?
• Stable?
30
O(n n)
yes
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Properties of Shellsort
• Fewer comparisons than insertion sort. Known to
be worst-case for good gap sequences.
• Conjectured to be O(n1.25) but the algorithm is very
hard to analyse.
• Very good on medium-sized arrays (up to size
10,000 or so).
• In-place?
• Stable?
30
O(n n)
yes
no
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Other Instances of Decrease-and-
Conquer by a Constant
• Insertion sort is a simple instance of the “decrease-
and-conquer by a constant” approach.
• Another is the approach to topological sorting that
repeatedly removes a source.
• In the next lecture we look at examples of
“decrease by some factor”, leading to methods
with logarithmic time behaviour or better!
31