Insertion Sort - Princeton University Computer Science

1 Robert Sedgewick and Kevin Wayne Copyright 2005 ~cos226 analysis of Algorithms2 Running TimeCharles Babbage (1864)As soon as an Analytic Engine exists, it will necessarilyguide the future course of the Science . Whenever anyresult is sought by its aid, the question will arise - By whatcourse of calculation can these results be arrived at by themachine in the shortest time? - Charles BabbageAnalytic Engine (schematic)3 OverviewAnalysis of algorithms: framework for comparing algorithms andpredicting method.!Observe some feature of the universe.!Hypothesize a model that is consistent with observation.!Predict events using the hypothesis.!Verify the predictions by making further observations.!Validate the theory by repeating the previous steps until thehypothesis agrees with the = Computer Study: SortingSorting problem:!

2 Given N items, rearrange them in ascending order.!Applications: statistics, databases, data compression, computationalbiology, Computer graphics, scientific computing, ..HanleynameHaskellHauserHayesHongHornet HsuHausernameHongHsuHayesHaskellHanleyHo rnet5 Insertion sort .!Brute-force sorting solution.!Move left-to-right through array.!Exchange next element with larger elements to its left, Sortpublic static void insertionSort(double[] a) { int N = ; for (int i = 0; i < N; i++) { for (int j = i; j > 0; j--) { if (less(a[j], a[j-1])) exch(a, j, j-1); else break; } }}6 Insertion sort : ObservationObserve and tabulate running time for various values of N.!Data source: N random numbers between 0 and million40,00099 million20,00025 million10, million5,000 ComparisonsN16 million80,0007 Data analysis .

3 Plot # comparisons vs. input size on log-log Fit line through data points ! a # comparisons grows quadratically with input size ! N2 sort : Experimental Hypothesisslope8 Insertion sort : Prediction and VerificationExperimental hypothesis. # comparisons ! N2 400 million comparisons for N = 40, 10 billion comparisons for N = 200, billion200, million40, million40, million40, million40, sort : Theoretical HypothesisExperimental hypothesis.!Measure running times, plot, and fit curve.!Model useful for predicting, but not for hypothesis.!Analyze algorithm to estimate # comparisons as a function of: number of elements N to sort average or worst case input!Model useful for predicting and explaining.!Model is independent of a particular machine or Theoretical model can apply to machines not yet sort : Theoretical HypothesisWorst case.

4 (descending)!Iteration i requires i comparisons.!Total = 0 + 1 + 2 + .. + N-2 + N-1 = N (N-1) / case. (random)!Iteration i requires i/2 comparisons on average.!Total = 0 + 1/2 + 2/2 + .. + (N-1)/2 = N (N-1) / sort : Theoretical HypothesisTheoretical Theory agrees with / 4N2 / 2 NComparisons1/6 N3/2--Stddev12 Insertion sort : ObservationObserve and tabulate running time for various values of N.!Data source: N random numbers between 0 and 1.!Machine: Apple G5 with memory running OS seconds400 million40, seconds99 million20, seconds25 million10, million5,00023 secondsTimeComparisonsN16 million80,000145 seconds10 billion200,00013 Data analysis . Plot time vs. input size on log-log Fit line through data points ! a Running time grows quadratically with input sort : Experimental Hypothesis14 Timing in JavaWall clock.

5 Measure time between beginning and end of computation.!Manual: Skagen wristwatch.!Automatic: ();..double elapsed = ();public class Stopwatch { private static long start; public static void tic() { start = (); } public static double toc() { long stop = (); return (stop - start) / ; }}15 Measuring Running TimeFactors that affect running time.!Machine.!Compiler.!Algorithm.!Inpu t factors.!Caching.!Garbage collection.!Just-in-time compilation.!CPU used by other line. Often hard to get precise of algorithms: framework for comparing algorithms andpredicting method.!Observe some feature of the universe.!Hypothesize a model that is consistent with observation.!Predict events using the hypothesis.!Verify the predictions by making further observations.!Validate the theory by repeating the previous steps until thehypothesis agrees with the question.

6 How to formulate a hypothesis?Robert Sedgewick and Kevin Wayne Copyright 2005 ~cos226 How To Formulate a Hypothesis18 Types of HypothesesWorst case running time. Obtain bound on largest possible running timeof algorithm on input of a given size N.!Generally captures efficiency in practice.!Draconian view, but hard to find effective case running time. Obtain bound on running time of algorithmon random input as a function of input size N.!Hard to accurately model real instances by random distributions.!Algorithm tuned for a certain distribution may perform poorly onother running time. Obtain bound on running time of sequence ofN operations as a function of the number of the Running TimeTotal running time: sum of cost " frequency for all of the basic ops.!Cost depends on machine, compiler.

7 !Frequency depends on algorithm, for sorting.!A = # exchanges.!B = # comparisons.!Cost on a typical machine = 11A + of sorting ops.!N = # elements to sort .!Selection sort : A = N-1, B = N(N-1) Knuth1974 Turing Award20An easier alternative.(i) Analyze asymptotic growth as a function of input size N.(ii) For medium N, run and measure time.(iii) For large N, use (i) and (ii) to predict growth rates.!Estimate as a function of input size N. N, N log N, N2, N3, 2N, N!!Ignore lower order terms and leading coefficients. Ex. 6N3 + 17N2 + 56 is asymptotically proportional to N3 Asymptotic Running Time21 Big Theta, Oh, and Omega notation.!#(N2) means { N2, 17N2, N2 + + 3N, .. } ignore lower order terms and leading coefficients!O(N2) means { N2, 17N2, N2 + + 3N, , 100N, .. } #(N2) and smaller use for upper bounds!

8 $(N2) means { N2, 17N2, N2 + + 3N, N3, 100N5, .. } #(N2) and larger use for lower boundsNever say: Insertion sort makes at least O(N2) Oh Notation22 Why It Matters1000 Time tosolve aproblemof size10,000100,000million10 seconds22 minutes15 days41 years41 millennia9203,60014,00041,0001,000 Run time innanoseconds --> N3secondMax sizeproblemsolvedin oneminutehourday10 msec1 weeks10,00077,000600, million10010 msec6 msec78 seconds11 seconds1 million49 trillion50 trillion10+47 N msec48 seconds21 billion76 trillion1,800 trillion1048 NN multiplied by 10,time multiplied byReference: More Programming Pearls by Jon Bentley23 Orders of Magnitude10-10 Meters in / decadeImperialUnits1 ft / in / ft / hour2 ft / mi / hour220 mi / hourContinental driftExampleHair growingGlacierGastro-intestinal tractAntHuman walkPropeller airplane104106108370 mi / min620 mi / sec62,000 mi / secSpace shuttleEarth in galactic orbit1/3 speed of light1 Seconds10210310410510610710810910101 minutes17 centuriesforever1017age ofuniverse.

9 1010 seconds210thousand220million230billionPo wersof 2 Reference: More Programming Pearls by Jon Bentley24 Constant TimeLinear time. Running time is O(1).Elementary operations.!Function call.!Boolean operation.!Arithmetic operation.!Assignment statement.!Access array element by TimeLogarithmic time. Running time is O(log N).Searching in a sorted list. Given a sorted array of items, find index ofquery (log N) solution. Binary static int binarySearch(String[] a, String key) { int left = 0; int right = - 1; while (left <= right) { int mid = (left + right) / 2; int cmp = (a[mid]); if (cmp < 0) right = mid - 1; else if (cmp > 0) left = mid + 1; else return mid; } return -1;}26 Linear TimeLinear time. Running time is O(N).Find the maximum. Find the maximum value of N items in an max = ;for (int i = 0; i < N; i++) { if (a[i] > max) max = a[i];}27 Linearithmic TimeLinearithmic time.

10 Running time is O(N log N).Sorting. Given an array of N elements, rearrange in ascending (N log N) solution. Mergesort. [stay tuned]Remark. $(N log N) comparisons required. [stay tuned]28 Quadratic TimeQuadratic time. Running time is O(N2).Closest pair of points. Given a list of N points in the plane, find thepair that is (N2) solution. Enumerate all pairs of $(N2) seems inevitable, but this is just an min = ;for (int i = 0; i < N; i++){ for (int j = i+1; j < N; j++) { double dx = (x[i] - x[j]); double dy = (y[i] - y[j]); if (dx*dx + dy*dy < min) min = dx*dx + dy*dy; }}29 Exponential TimeExponential time. Running time is O(aN) for some constant a > sequence: 1 1 2 3 5 8 13 21 34 55 ..O(%N) solution. Spectacularly inefficient!Efficient static int F(int N) { if (n == 0 || n == 1) return n; else return F(n-1) + F(n-2);}!