New version page

Princeton COS 226 - Radix Sorts

Documents in this Course
QUICKSORT

QUICKSORT

14 pages

QUICKSORT

QUICKSORT

55 pages

STRINGS

STRINGS

69 pages

Lecture

Lecture

4 pages

STRINGS

STRINGS

18 pages

Hashing

Hashing

7 pages

MERGESORT

MERGESORT

14 pages

Quicksort

Quicksort

12 pages

Strings

Strings

10 pages

Overview

Overview

15 pages

Hashing

Hashing

13 pages

Mergesort

Mergesort

15 pages

Tries

Tries

13 pages

Final

Final

12 pages

Final

Final

12 pages

Mergesort

Mergesort

13 pages

Final

Final

10 pages

Load more
Upgrade to remove ads

This preview shows page 1-2-3-4-5 out of 14 pages.

Save
View Full Document
Premium Document
Do you want full access? Go Premium and unlock all 14 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 14 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 14 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 14 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 14 pages.
Access to all documents
Download any document
Ad free experience

Upgrade to remove ads
Unformatted text preview:

Algorithms in Java, 4th Edition·Robert Sedgewick and Kevin Wayne·Copyright © 2008·April 7, 2008 11:01:38 AMRadix SortsReferences: Algorithms in Java, Chapter 10 http://www.cs.princeton.edu/algs4/61radix‣key-indexed counting‣LSD radix sort‣MSD radix sort‣3-way radix quicksort‣longest repeated substringReview: summary of the performance of sorting algorithmsNumber of operations.Lower bound. N lg N -1.44 N compares are required by any algorithm.Q. Can we do better (despite the lower bound)?A. Yes, if we don't depend on compares.2algorithmguaranteeaverageextra spaceoperations on keysinsertion sortN2 /2N2 /4nocompareTo()selection sortN2 /2N2 /2nocompareTo()mergesortN lg NN lg NNcompareTo()quicksort1.39 N lg N1.39 N lg Nc lg NcompareTo()Digital keysDigital key. Sequence of digits over fixed alphabet.Radix. Number of digits in alphabet.Applications.•DNA: sequence of a, c, g, t.•IPv6 address: sequence of 128 bits.•English words: sequence of lowercase letters.•Protein: sequence of amino acids A, C, ..., Y.•Credit card number: sequence of 16 decimal digits.•International words: sequence of Unicode characters.•Library call numbers: sequence of letters, numbers, periods.This lecture. String of ASCII characters.34‣key-indexed counting‣LSD radix sort‣MSD radix sort‣3-way radix quicksort‣longest repeated substringKey-indexed counting: assumptions about keysAssumption. Keys are integers between 0 and R-1.Implication. Can use key as an array index.Applications.•Sort string by first letter.•Sort class roster by precept.•Sort phone numbers by area code.•Subroutine in a sorting algorithm.5Goal. Sort an array a[] of N integers between 0 and R-1.•Count frequencies of each letter using key as index.• • • int N = a.length; int[] count = new int[R+1]; for (int i = 0; i < N; i++) count[a[i]+1]++; for (int r = 0; r < R; k++) count[r+1] += count[r]; for (int i = 0; i < N; i++) temp[count[a[i]]++] = a[i]; for (int i = 0; i < N; i++) a[i] = temp[i];a0b2c3d1e2f1-36Key-indexed countingi a[i]0d1a2c3f4f5b6d7b8f9b10e11ar count[r]countfrequenciesoffset by 1[stay tuned]Goal. Sort an array a[] of N integers between 0 and R-1.•Count frequencies of each letter using key as index.•Compute frequency cumulates which specify destinations.• •a0b2c5d6e8f9-127Key-indexed countingi a[i]0d1a2c3f4f5b6d7b8f9b10e11ar count[r]computecumulates int N = a.length; int[] count = new int[R+1]; for (int i = 0; i < N; i++) count[a[i]+1]++; for (int r = 0; r < R; r++) count[r+1] += count[r]; for (int i = 0; i < N; i++) temp[count[a[i]]++] = a[i]; for (int i = 0; i < N; i++) a[i] = temp[i]; 6 keys < d, 8 keys < eso d’s go in a[6] and a[7]Goal. Sort an array a[] of N integers between 0 and R-1.•Count frequencies of each letter using key as index.•Compute frequency cumulates which specify destinations.•Access cumulates using key as index to move records.• int N = a.length; int[] count = new int[R+1]; for (int i = 0; i < N; i++) count[a[i]+1]++; for (int r = 0; r < R; k++) count[r+1] += count[r]; for (int i = 0; i < N; i++) temp[count[a[i]]++] = a[i]; for (int i = 0; i < N; i++) a[i] = temp[i];a2b5c6d8e9f12-128Key-indexed countingi a[i]0d1a2c3f4f5b6d7b8f9b10e11amoverecords0a1a2b3b4b5c6d7d8e9f10f11fi temp[i]r count[r]Goal. Sort an array a[] of N integers between 0 and R-1.•Count frequencies of each letter using key as index.•Compute frequency cumulates which specify destinations.•Access cumulates using key as index to move records.•Copy back into original array. int N = a.length; int[] count = new int[R+1]; for (int i = 0; i < N; i++) count[a[i]+1]++; for (int r = 0; r < R; k++) count[r+1] += count[r]; for (int i = 0; i < N; i++) temp[count[a[i]]++] = a[i]; for (int i = 0; i < N; i++) a[i] = temp[i];a2b5c6d8e9f12-129Key-indexed countingi a[i]0a1a2b3b4b5c6d7d8e9f10f11fcopyback0a1a2b3b4b5c6d7d8e9f10f11fi temp[i]r count[r]Key-indexed counting: analysisAssumption. Keys are integers between 0 and R-1.Running time. Takes time proportional to N + R.Extra space.•Array of size R (for counting).•Array of size N (for rearrangement).Stability. Yes!10inplace version is possible and practical11‣key-indexed counting‣LSD radix sort‣MSD radix sort‣3-way radix quicksort‣longest repeated substringLeast-significant-digit-first radix sortLSD radix sort.•Consider characters from right to left.•Stably sort using dth character as the key via key-indexed counting.120dab1add2cab3fad4fee5bad6dad7bee8fed9bed10ebb11ace0dab1cab2ebb3add4fad5bad6dad7fed8bed9fee10bee11acesort must be stable(arrows do not cross)sort key0dab1cab2fad3bad4dad5ebb6ace7add8fed9bed10fee11beesort key0ace1add2bad3bed4bee5cab6dab7dad8ebb9fad10fed11feesort key13LSD radix sort: correctness proofProposition. LSD sorts fixed-length strings in ascending order.Pf. [thinking about the future]•If the characters not yet examined differ,it doesn't matter what we do now.•If the characters not yet examined agree,stability ensures later pass won't affect order.0dab1cab2fad3bad4dad5ebb6ace7add8fed9bed10fee11bee0ace1add2bad3bed4bee5cab6dab7dad8ebb9fad10fed11feesort keyin orderby previous passesAssumption. Radix R, fixed-length W keys.14LSD radix sort: Java implementationkey-indexed countingpublic static void lsd(String[] a){ int N = a.length; String[] temp = new String[N]; for (int d = W-1; d >= 0; d--) { int[] count = new int[R+1]; for (int i = 0; i < N; i++) count[a[i].charAt(d) + 1]++; for (int r = 0; r < R; r++) count[r+1] += count[r]; for (int i = 0; i < N; i++) temp[count[a[i].charAt(d)]++] = a[i]; for (int i = 0; i < N; i++) a[i] = temp[i]; }}do key-indexed countingfor each digit from right to leftSummary of the performance of sorting algorithmsFrequency of operations.15algorithmguaranteeaverageextra spaceoperations on keysinsertion sortN2 /2N2 /4nocompareTo()selection sortN2 /2N2 /2nocompareTo()mergesortN lg NN lg NNcompareTo()quicksort1.39 N lg N1.39 N lg Nc lg NcompareTo()LSD †W NW NN + RcharAt() † fixed-length W keysProblem. Sort a huge commercial database on a fixed-length key field.Ex. Account number, date, SS number, ...Which sorting method to use?•Insertion sort.•Mergesort.•Quicksort.•LSD radix sort.16Sorting


View Full Document
Download Radix Sorts
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 Sorts 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 Sorts 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?