COMPSCI 61B Lecture Notes - Lecture 33: Heapsort, Insertion Sort, Sorting Algorithm
28 Aug 2017
School
Department
Course
Professor
Document Summary
Read 1,000,000 integers from a le into an array of length 1,000,000. Insertion sort (n), which does n swaps when there are n inversions (runtime is proportional to amount of work required to be done) On arrays with a small number of inversions, insertion sort is extremely fast. One exchange per inversion (and number of comparisons is similar) runtime is. (n + k) where k is number of inversions. De ne an almost sorted array as one in which number of inversions cn for some c insertion sort is excellent on these arrays. Less obvious: for small arrays (n < 15 or so), insertion sort is fastest. More of an empirical fact than a theoretical one. Rough idea: divide and conquer algorithms like heapsort and mergesort spend too much time dividing, whereas insertion sort goes straight to the conquest. Selection sort: find the smallest item and put it at the front.
