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
Unlocking...