Comparison Sorts IIICS 311 Data Structures and AlgorithmsLecture SlidesWednesday, October 14, 2009Glenn G. ChappellDepartment of Computer ScienceUniversity of Alaska [email protected]© 2005–2009 Glenn G. Chappell14 Oct 2009 CS 311 Fall 2009 2Unit OverviewAlgorithmic Efficiency & SortingMajor Topics Introduction to Analysis of Algorithms Introduction to Sorting Comparison Sorts I More on Big-O The Limits of Sorting Divide-and-Conquer Comparison Sorts II Comparison Sorts III Radix Sort Sorting in the C++ STL14 Oct 2009 CS 311 Fall 2009 3ReviewIntroduction to Analysis of AlgorithmsEfficiency General: using few resources (time, space, bandwidth, etc.). Specific: fast (time).Analyzing Efficiency Determine how the size of the input affects running time, measured in steps, in the worst case.Scalable: works well with large problems.Exponential timeO(bn), for some b > 1Quadratic timeO(n2)Log-linear timeO(n log n)Linear timeO(n)Logarithmic timeO(log n)Constant timeO(1)In WordsUsing Big-OCannot read all of inputProbably not scalableFasterSlower14 Oct 2009 CS 311 Fall 2009 4ReviewIntroduction to Sorting — Basics, Analyzing Sort: Place a collection of data in order.Key: The part of the data item used to sort.Comparison sort: A sorting algorithmthat gets its information by comparingitems in pairs.A general-purpose comparison sortplaces no restrictions on the size of thelist or the values in it.Five criteria for analyzing a general-purpose comparison sort: (Time) Efficiency Requirements on Data Space Efficiency Stability Performance on Nearly Sorted DataIn-place = no large additional space required.1. All items close to proper places,OR2. few items out of order.3 1 3 5 251 2 3 5 53xyx<y?compareStable = never changes the order of equivalent items.14 Oct 2009 CS 311 Fall 2009 5ReviewIntroduction to Sorting — Overview of AlgorithmsThere is no known sorting algorithm that has all the properties we would like one to have.We will examine a number of sorting algorithms. Most of these fall into two categories: O(n2) and O(n log n). Quadratic-Time [O(n2)] Algorithms Bubble Sort Insertion Sort Quicksort Treesort (later in semester) Log-Linear-Time [O(n log n)] Algorithms Merge Sort Heap Sort (mostly later in semester) Introsort (not in the text) Special Purpose — Not Comparison Sorts Pigeonhole Sort Radix Sort14 Oct 2009 CS 311 Fall 2009 6ReviewComparison Sorts I — Insertion Sort: IllustrationItems to left of bold bar are sorted.Bold item = item to be inserted into sorted section.5 8 2 5 266 8 2 5 256 8 2 5 25Insert 5Insert 95 6 8 5 225 5 6 8 222 5 5 6 82Insert 5Insert 2Two 5s!Two 2s!unsortedsorted5 6 8 5 22Insert 25555552 5 5 5 62Insert 5SortedAnother 5!85A list of size 1 is always sorted14 Oct 2009 CS 311 Fall 2009 7ReviewComparison Sorts I — Insertion Sort: Analysis(Time) Efficiency  Insertion Sort is O(n2). Insertion Sort also has an average-case time of O(n2). Requirements on Data ☺ Insertion Sort does not require random-access data. It works on Linked Lists.*Space Efficiency ☺ Insertion Sort can be done in-place.*Stability ☺ Insertion Sort is stable.Performance on Nearly Sorted Data ☺ (1) Insertion Sort can be written to be O(n) if each item is at most some constant distance from its proper place.* (2) Insertion Sort can be written to be O(n) if only a constant number of items are out of place.*For one-way sequential-access data (e.g., Linked Lists) we give up EITHER in-place OR O(n) on type (1) nearly sorted data.14 Oct 2009 CS 311 Fall 2009 8ReviewComparison Sorts I — Insertion Sort: CommentsInsertion Sort is too slow for general-purpose use.However, Insertion Sort is useful in certain special cases. Insertion Sort is fast (linear time) for nearly sorted data. Insertion Sort is also considered fast for small lists.Insertion Sort often appears as part of another algorithm. Most good sorting methods call Insertion Sort for small lists. Some sorting methods get the data nearly sorted, and then finishwith a call to Insertion Sort. (More on this later.)14 Oct 2009 CS 311 Fall 2009 9ReviewMore on Big-OThree ways to talk about how fast a function grows. g(n) is: O(f(n)) if g(n) ≤ k × f(n) … Ω(f(n)) if g(n) ≥ k × f(n) … Θ(f(n)) if both of the above are true. Possibly with different values of k.Useful: Let g(n) be the max number of steps required by some algorithm when given input of size n.Or: Let g(n) be the max amount of additional space required when given input of size n.14 Oct 2009 CS 311 Fall 2009 10ReviewThe Limits of Sorting [1/2]Sorting is determining the ordering of a list. Many orderings are possible.Each time we do a comparison, we find the relative order of two items. Say x < y; we can throw out all orderings in which y comes before x.We cannot stop until only one possible ordering is left.Example Bubble Sort the list 2 3 1.Possibleorderings:123 132213 231312 3213 < 2No?Possibleorderings:123 132213 231312 3211 < 3Yes?Possibleorderings:123 132213 231312 3211 < 2Yes?Possibleorderings:123 132213 231312 321231231213123Bubble SortComparisonsAlternate ViewPass 2Pass 114 Oct 2009 CS 311 Fall 2009 11ReviewThe Limits of Sorting [2/2]I have said that good sorting algorithms are O(n log n).We showed that a general-purpose comparison sort cannot do better than this.In particular, a general purpose comparison sort must doΩ(n log n) comparisons, in the worst case. The proof is based on the idea on the previous slide. A list of n items has n! possible orderings. In order to reduce this down to just one ordering, at least log2(n!) comparisons, are required, in the worst case. And log2(n!) is Ω(n log n).14 Oct 2009 CS 311 Fall 2009 12ReviewDivide-and-ConquerA common algorithmic strategy is called divide-and-conquer: split the input into pieces, and handle these with recursive calls.If an algorithm using divide-and-conquer splits the input into nearly equal-sized parts, then we can analyze it using the Master Theorem. b is the number of nearly equal-sized parts. bkis the number of recursive calls. Find k. f(n) is the amount of extra work done (number of steps). Hopefully, f(n) looks like n raised to some power. If the power is less than k, then the algorithm is O(nk). If the power is k, then the algorithm is Θ(nklog