UAF CS 311 - Radix Sort Sorting in the C++ STL

Unformatted text preview:

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++ STL16 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
Download Radix Sort Sorting in the C++ STL
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Radix Sort Sorting in the C++ STL and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Radix Sort Sorting in the C++ STL 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?