程序代写代做代考 algorithm 09.key

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)

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.

Sorting n items

23 9 52 12 41 83 46A:
0 1 2 3 4 5 6

Sorting n items

23 9 52 12 41 83 46A:
0 1 2 3 4 5 6

Sort first n-1 items

Sorting n items

23 9 52 12 41 83 46A:
0 1 2 3 4 5 6

Sort first n-1 items

Sorting n items

9 12 23 41 52 83 46A:
0 1 2 3 4 5 6

Sorting n items

9 12 23 41 52 83 46A:
0 1 2 3 4 5 6

Sorting n items

9 12 23 41 83 46A:
0 1 2 3 4 5 6

Sorting n items

9 12 23 41 83 46A:
0 1 2 3 4 5 6

Sorting n items

9 12 23 41 83 46A:
0 1 2 3 4 5 6

Sorting n items

9 12 23 41 83 46A:
0 1 2 3 4 5 6

Sorting n items

9 12 23 41 8346A:
0 1 2 3 4 5 6

Sorting n items

9 12 23 41 52 83 46A:
0 1 2 3 4 5 6

Sorting n items

9 12 23 41 52 83 46A:
0 1 2 3 4 5 6

v: 46

Sorting n items

9 12 23 41 52 83 46A:
0 1 2 3 4 5 6

v: 46

A[j]

Sorting n items

9 12 23 41 52 83 83A:
0 1 2 3 4 5 6

v: 46

A[j]

Sorting n items

9 12 23 41 52 83 83A:
0 1 2 3 4 5 6

v: 46

A[j]

Sorting n items

9 12 23 41 52 52 83A:
0 1 2 3 4 5 6

v: 46

A[j]

Sorting n items

9 12 23 41 52 52 83A:
0 1 2 3 4 5 6

v: 46

A[j]

Sorting n items

9 12 23 41 46 52 83A:
0 1 2 3 4 5 6

v: 46

A[j]

Sorting n items

9 12 23 41 46 52 83A:
0 1 2 3 4 5 6

v: 46

A[j]

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

• 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

Related Posts