COMPSCI 61B Lecture Notes - Lecture 33: Quicksort, Big O Notation, Merge Sort
1 Jun 2017
School
Department
Course
Professor
Document Summary
Saturday 4/15: guerilla section will be held 12-2 pm in 2nd oor labs, covers graphs and sorting. Start today if you haven"t started yet, not a project you can do last minute. Slides and videos are available to help speed you through getting started. Extra credit deadline is sunday, covers only rastering. Don"t have an insert operation when building your quadtree. Unlike a general quadtree, you know exactly what you"re getting in advance. Interestingly, insertion sort can be bounded by the number of inversions. Runtime is proportional to how much work needs to be done. On arrays with a small number of inversions, insertion sort is extremely fast. Runtime is theta(n + k), where k is the number of inversions. De ne an almost sorted array as one in which number of inversions <= cn for some c. For small arrays (n < 15 or so), insertion sort is fastest. More of an empirical fact than a theoretical one.
