Radix SortSorting in the C++ STLCS 311 Data Structures and AlgorithmsLecture SlidesMonday, March 16, 2009Glenn G. ChappellDepartment of Computer ScienceUniversity of Alaska [email protected]© 2005–2009 Glenn G. Chappell16 Mar 2009 CS 311 Spring 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++ STL16 Mar 2009 CS 311 Spring 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 inputFasterSlowerUsually too slow to be scalable16 Mar 2009 CS 311 Spring 2009 4ReviewIntroduction to Sorting — Basics, Analyzing Sort: Place a list 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 storage space required (constant additional space).1. All items close to properplaces, OR2. few items out of order.3 1 3 5 251 2 3 5 53xyx<y?compare16 Mar 2009 CS 311 Spring 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 Selection 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)16 Mar 2009 CS 311 Spring 2009 6ReviewComparison Sorts III — Quicksort: DescriptionQuicksort is another divide-and-conquer algorithm. Procedure:• Chooses a list item (the pivot).• Do a Partition: put items less than the pivot before it, and items greater than the pivot after it.• Recursively sort two sublists: items before 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 give us 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 Mar 2009 CS 311 Spring 2009 7ReviewComparison Sorts III — Quicksort: ImprovementsUnoptimized Quicksort is slow (quadratic time) on nearly sorted data and uses a lot of space (linear) for recursion.Three Improvements • Median-of-three pivot selection. Improves performance on mostnearly sorted data. Requires random-access data.• Tail-recursion elimination onlarger 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:We wrote these two.16 Mar 2009 CS 311 Spring 2009 8ReviewComparison Sorts III — Quicksort: AnalysisEfficiency • 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-three and others) are only efficient for random-access data.Space Usage • Quicksort uses space for recursion. Additional space: O(log n), if you are clever about it. Even if all recursion is eliminated, O(log n) additional space is used. This additional space need not hold any data items.Stability • Efficient versions of Quicksort are not stable.Performance on Nearly Sorted Data • A non-optimized Quicksort is slow on nearly sorted data: O(n2).• Median-of-three Quicksort is O(n log n) on most nearly sorted data.16 Mar 2009 CS 311 Spring 2009 9ReviewComparison 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.16 Mar 2009 CS 311 Spring 2009 10ReviewComparison 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 sublist.Introsort-recurseLike Mo3 Quicksort:Find Mo3 Pivot, PartitionIntrosort-recurseLike Mo3 Quicksort:Find Mo3 Pivot, PartitionRecursion Depth LimitNow, the list is nearly sorted. Finish with a (linear time!) Insertion Sort [??].Heap Sort Heap SortTail recursion eliminated. (But it still counts toward the maximum recursion depth.)16 Mar 2009 CS 311 Spring 2009 11ReviewComparison Sorts III — Introsort: AnalysisEfficiency ☺☺• Introsort is O(n log n).• Introsort also has an average-case time of O(n log n) [of course].
View Full Document