Radix SortSorting in the C++ STLCS 311 Data Structures and AlgorithmsLecture SlidesMonday, October 19, 2009Glenn G. ChappellDepartment of Computer ScienceUniversity of Alaska [email protected]© 2005–2009 Glenn G. Chappell19 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19 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 scalableFasterSlower19 Oct 2009 CS 311 Fall 2009 4ReviewIntroduction to Sorting — BasicsSort: 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.3 1 3 5 251 2 3 5 53xyx<y?compare19 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(some) 19 Oct 2009 CS 311 Fall 2009 6ReviewComparison 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 Merge19 Oct 2009 CS 311 Fall 2009 7ReviewComparison 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 53PartitionPivotPivot319 Oct 2009 CS 311 Fall 2009 8ReviewComparison Sorts III — Better Quicksort: OptimizationsUnoptimized Quicksort is slow (quadratic time) on nearly sorted data and uses a lot of space (linear) for recursion.We discussed three optimizations:  Median-of-three pivot selection. Improves performance on mostnearly sorted data. Requires random-access data. Tail-recursion elimination on thelarger recursive call. Reduces space usage to logarithmic. Do not sort small sublists; finish with Insertion Sort. General speed up. May adversely affect cache hits.With these optimizations, Quicksort is still O(n2) time.12 9 3 12 10 6101 3 122 96PivotAfter Partition:Initial State:Median-of-three19 Oct 2009 CS 311 Fall 2009 9ReviewComparison Sorts III — Better Quicksort: Analysis of QuicksortEfficiency  Quicksort is O(n2). Quicksort has a very good O(n log n) average-case time. ☺☺Requirements on Data  Non-trivial pivot-selection algorithms (median-of-3 and others) are only efficient for random-access data.Space Usage  Quicksort uses space for recursion. Additional space: O(log n), if clever tail-recursion elimination is done. Even if all recursion is eliminated, O(log n) additional space is still used. This additional space need not hold any data items.Stability  Efficient versions of Quicksort are not stable.Performance on Nearly Sorted Data  An unoptimized Quicksort is slow on nearly sorted data: O(n2). Quicksort + median-of-3 is O(n log n) on most nearly sorted data.Unlike Merge Sort19 Oct 2009 CS 311 Fall 2009 10ReviewComparison Sorts III — Introsort: DescriptionIn 1997, David Musser found out how to make Quicksort log-linear time. Keep track of the recursion depth. If this exceeds some bound (recommended: 2 log2n), then switch to Heap Sort for the current sublist. Heap Sort is a general-purpose comparison sort that is log-linear time and in-place. We will discuss it in detail later in the semester. Musser calls this technique “introspection”. Thus, introspectivesorting, or Introsort.19 Oct 2009 CS 311 Fall 2009 11ReviewComparison Sorts III — Introsort: DiagramHere is an illustration of how Introsort works. In practice, the recursion will be deeper than this. The Insertion-Sort call might not be done, due to its effect on cache hits.Introsort-recurseLike Mo3 Quicksort:Find Mo3 Pivot, PartitionIntrosort-recurseLike Mo3 Quicksort:Find Mo3 Pivot, PartitionIntrosort-recurseLike Mo3 Quicksort:Find Mo3 Pivot, PartitionIntrosort-recurseLike Mo3 Quicksort:Find Mo3 Pivot, PartitionIntrosort-recurseLike Mo3 Quicksort:Find Mo3 Pivot, PartitionInsertion SortIntrosortWhen the sublist to sort is very small, do not recurse. Insertion Sort will finish the job later [??].When the recursion depth is too great, switch to Heap Sort to sort the current