Comparison Sorts IIICS 311 Data Structures and AlgorithmsLecture SlidesFriday, October 16, 2009Glenn G. ChappellDepartment of Computer ScienceUniversity of Alaska [email protected]© 2005–2009 Glenn G. Chappellcontinued16 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(part)16 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 scalableFasterSlower16 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.16 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(part)16 Oct 2009 CS 311 Fall 2009 6ReviewComparison Sorts I — Insertion SortInsertion Sort repeatedly does this:Analysis Efficiency: O(n2). Average case same.  Requirements on data: Works for Linked Lists, etc. ☺ Space Efficiency: In-place. ☺ Stable: Yes. ☺ Performance on Nearly Sorted Data: O(n) for both kinds. ☺Notes Too slow for general-purpose use. Works well on nearly sorted data and small lists. Thus, used as part of other algorithms.xsorted unsortedinsert16 Oct 2009 CS 311 Fall 2009 7ReviewMore on Big-O, The Limits of SortingThree 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.In an algorithmic context, g(n) might be the max number of steps required by some algorithm when given input of size n, or the max amount of additional space required.Fact. Every general-purpose comparison sort does Ω(n log n) comparisons in the worst case.16 Oct 2009 CS 311 Fall 2009 8ReviewDivide-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 n).Important!16 Oct 2009 CS 311 Fall 2009 9ReviewComparison Sorts II — Merge SortMerge Sort splits the data in half, recursively sorts each half, and then merges the two.Stable Merge Linear time, stable. In-place for Linked List. Uses buffer[O(n) space] for array.Analysis Efficiency: O(n log n). Average same. ☺ Requirements on data: Works forLinked Lists, etc. ☺ Space Efficiency: O(log n) space forLinked List. Can eliminate recursion tomake this in-place. O(n) space for array./☺/ Stable: Yes. ☺ Performance on Nearly Sorted Data: Not better or worse. Notes Practical & often used. Fastest known for (1) stable sort, (2) sorting a Linked List. Good standard for judging sorting algorithms3 1 3 5 25 31 3 2 3 35 51 2 3 3 53 5Sort (recurse)Sort (recurse)Stable Merge16 Oct 2009 CS 311 Fall 2009 10ReviewComparison Sorts III — Quicksort: Introduction, PartitionQuicksort is another divide-and-conquer algorithm. Procedure: Choose a list item (the pivot). Do a Partition: put items less thanthe pivot before it, and items greaterthan the pivot after it. Recursively sort two sublists: itemsbefore pivot, items after pivot.We did a simple pivot choice: thefirst item. Later, we improve this.Fast Partition algorithms are in-place,but not stable. Note: In-place Partition does not giveus an in-place Quicksort. Quicksort uses memory for recursion.1 3 5 25 33Sort (recurse)Sort (recurse)1 3 52 5 32 3 31 5 53PartitionPivotPivot316 Oct 2009 CS 311 Fall 2009 11ReviewComparison Sorts III — Quicksort: Write ItTO DO Write Quicksort, with the in-place Partition being a separate function.Done. See quicksort1.cpp, on the web page.16 Oct 2009 CS 311 Fall 2009 12ReviewComparison Sorts III — Better Quicksort: ProblemQuicksort has a problem. In the worst case, the pivot is chosen poorly. Thus: linear recursion depth, and so Quicksort is O(n2).  And the worst case happens when the list is already sorted!However, Quicksort’s average-case time is very fast. This is O(n log n) and typically significantly faster than Merge Sort.Quicksort is usually very fast; thus, people want to use it. So we try to figure out how to make it better. We look at three of the best optimizations …16 Oct 2009 CS 311 Fall 2009 13ReviewComparison Sorts