WIXLIB

Stably sorting a set of cards by suitKey-indexed al. 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 items.・Copy back into original array.int N a.length;int[] count new int[R];int[] pos new int[R];for (int i 0; i N; i )count[a[i]] ;for (int r 1; r R; r )pos[r] count[r-1] pos[r-1];for (int i 0; i N; i )aux[pos[a[i]] ] a[i];for (int i 0; i N; i )a[i] aux[i];4142Key-indexed countingKey-indexed countingGoal. Sort an array a[] of N integers between 0 and R - 1.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 items.・Copy back into original array.・Count frequencies of each letter using key as index.・Compute frequency cumulates which specify destinations.・Access cumulates using key as index to move items.・Copy back into original array.int N a.length;int[] count new int[R];int[] pos new int[R];for (int i 0; i N; i )count[a[i]] ;Q. Modify this code to sort an arrayint N a.length;int[] count new int[R];int[] pos new int[R];a[] of Objects, assuming a key()method that returns int between0 and R-1.for (int i 0; i N; i )count[a[i].key() 1] ;for (int r 1; r R; r )Q. Modify this code to sort an arraya[] of Objects, assuming a key()method that returns int between0 and R-1.for (int r 1; r R; r )pos[r] count[r-1] pos[r-1];pos[r] count[r-1] pos[r-1];for (int i 0; i N; i )for (int i 0; i N; i )aux[pos[a[i]] ] a[i];aux[pos[a[i].key()] ] a[i];for (int i 0; i N; i )a[i] aux[i];for (int i 0; i N; i )a[i] aux[i];4344

Radix sorting: quiz 1Which of the following are properties of key-indexed counting?A.Running time proportionalN i R.0;for to(intB.Extra space proportional to N R.C.Stable.D.All of the above.E.I don't know.i N; i )aux[count[a[i].key(d)] ] a[i];1000001111222333333333count[]2 3 43 8 144 8 144 9 144 10 144 10 154 10 154 11 154 11 164 12 164 12 165 12 166 12 166 12 167 12 167 12 177 13 177 13 187 13 198 13 198 14 198 14 ThompsonWilson111222223333334444445.1 S TRING S ORTSaux[0]aux[1]aux[2]‣ strings in Java‣ key-indexed countingaux[3]aux[4]aux[5]aux[6]‣ LSD radix sortAlgorithmsaux[7]aux[8]aux[9]‣ MSD radix sortaux[10]aux[11]aux[12]‣ 3-way radix quicksortR OBERT S EDGEWICK K EVIN W AYNEaux[13]‣ suffix ux[16]aux[17]aux[18]aux[19]Distributing the data (records with key 3 highlighted)45Recall from midtermLeast-significant-digit-first string sortWe can sort an array by date by first sorting it by day, then by month, thenLSD string (radix) sort.by year, but only if we use a stable sorting algorithm.・Consider characters from right to left.・Stably sort using d character as the key (using key-indexed counting).thsort key (d 2)yyyymmddyyyymmddyyyyyyyyyyyymmmmmmddddddsort key (d 1)sort key (d eesort is stable(arrows do not cross)4748

LSD string sort: correctness proofLSD string sort: Java implementationProposition. LSD sorts fixed-length strings in ascending order.sort keyPf. [ by induction on i ]after pass iAfter pass i, strings are sorted by last i characters.0・If two strings differ on sort key,dab01cab2fad3barelative order.4dIf two strings agree on sort key,5stability keeps them in proper relative order.key-indexed sort puts them in 7dad8fed8ebb9bed9fad10fee10fed11bee11feepublic class LSD{public static void sort(String[] a, int W){int R 256;int N a.length;String[] aux 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 )aux[count[a[i].charAt(d)] ] a[i];for (int i 0; i N; i )a[i] aux[i];}Proposition. LSD sort is stable.do key-indexed countingfor each digit from right to leftkey-indexed counting}sorted fromPf. Key-indexed counting is stable.fixed-length W stringsradix Rprevious passes}(by induction)4950Summary of the performance of sorting algorithmsRadix sorting: quiz 2Frequency of operations.Which sorting method to use to sort 1 million 32-bit integers?algorithmguaranteerandomextra spacestable?A.Insertion sort.B.Mergesort.operations on keys01110110111011011101.1011101insertion sort½ N2¼ N21 compareTo()C.Quicksort.mergesortN lg NN lg NN compareTo()D.LSD radix sort.E.I don't know.quicksortheapsortLSD sort†1.39 N lg Nc lg NcompareTo()2 N lg N2 N lg N1compareTo()2 W (N R)2 W (N R)N R1.39 N lg N* charAt()* probabilistic† fixed-length W keysQ. What if strings are not all of same length?5152

String sorting interview questionSORT ARRAY OF 128-BIT NUMBERSProblem. Sort huge array of random 128-bit numbers.Ex. Supercomputer sort, internet router.01110110111011011101.1011101Which sorting method to use?・Insertion sort.・Mergesort.・Quicksort.・Heapsort.・LSD string sort.Google CEO Eric Schmidt interviews Barack Obama5354SORT ARRAY OF 128-BIT NUMBERSSORT ARRAY OF 128-BIT NUMBERSProblem. Sort huge array of random 128-bit numbers.Ex. Supercomputer sort, internet router.Problem. Sort huge array of random 128-bit numbers.Ex. Supercomputer sort, internet router.01110110111011011101.1011101Which sorting method to use?01110110111011011101.1011101Which sorting method to use?・・Mergesort.・Quicksort.・Heapsort. ・LSD string sort.・Insertion sort.・Mergesort.・Quicksort.・Heapsort. ・LSD string sort. Insertion sort.Divide each word into eight 16-bit “chars”Divide each word into eight 16-bit “chars”216 65,536 counters.Sort in 8 passes.216 65,536 countersLSD sort on leading 32 bits in 2 passesFinish with insertion sortExamines only 25% of the data5556

How to take a census in 1900s?How to get rich sorting in 1900s?1880 Census. Took 1500 people 7 years to manually process data.Punch cards. [1900s to 1950s]Herman Hollerith. Developed a tabulating and sorting machine.・Also useful for accounting, inventory, and business processes.・Primary medium for data entry, storage, and processing.・Use punch cards to record data (e.g., sex, age).・Machine sorts one column at a time (into one of 12 bins).・Typical question: how many women of age 20 to 30?Hollerith tabulating machine and sorterHollerith's company later merged with 3 others to form ComputingTabulating Recording Corporation (CTRC); company renamed in 1924.punch card (12 holes per column)1890 Census. Finished in 1 year (and under budget)!IBM 80 Series Card Sorter (650 cards per minute)5758LSD string sort: a moment in history (1960s)5.1 S TRING S ORTScard punchpunched cardscard readermainframeline printer‣ strings in Java‣ key-indexed countingnot directly relatedto sortingTo sort a card deck- start on right columnAlgorithms- put cards into hopper- machine distributes into bins- pick up cards (stable)R OBERT S EDGEWICK K EVIN W AYNE- move left one columnhttp://algs4.cs.princeton.edu- continue until sortedcard sorterLysergic Acid Diethylamide(Lucy in the Sky with Diamonds)59‣ LSD radix sort‣ MSD radix sort‣ 3-way radix quicksort‣ suffix arrays

Reverse LSDMost-significant-digit-first string sort・Consider characters from left to right.・Stably sort using d character as the key (using key-indexed counting).MSD string (radix) sort.・Partition array into R pieces according to first characterth(use key-indexed counting).sort key (d 0)sort key (d 1)・Recursively sort all strings that start with each charactersort key (d 2)(key-indexed counts delineate subarrays to 0feenot sorted!11ace11fedsort key61MSD string sort: urelythethefadfee11fed62Variable-length stringsTreat strings as if they had an extra char at end (smaller than any ellsaresurelyseashells910sort ssellssheshoreshellsshesurelythetheneed to examineevery characterin equal keysarearearearebybybybyseaseaseaseaseashells seashells seashells seashellsseashells seashells seashells relythetheend of stringgoes before anychar valuearearearebybybyseaseaseaseashells seashells seashellsseashells seashells lssellssellssheshoreshellsshesurelythethewhy hore-17surelylls-1she before lsshesheshellsshoresurelythetheprivate static int charAt(String s, int d){if (d s.length()) return s.charAt(d);else return -1;}C strings. Have extra char '\0' at end no extra work needed.Trace of recursive calls for MSD string sort (no cutoff for small subarrays, subarrays of size 0 and 1 omitted)6364

MSD string sort: Java implementationMSD string sort: potential for disastrous performancecount[]Observation 1. Much too slow for small subarrays.public static void sort(String[] a){・Each function call needs its own count[] array.・ASCII (256 counts): 100x slower than copy pass for N 2.・Unicode (65,536 counts): 32,000x slower for N 2.recycles aux[] arraybut not count[] arrayaux new String[a.length];sort(a, aux, 0, a.length - 1, 0);}Observation 2. Huge number of small subarraysprivate static void sort(String[] a, String[] aux, int lo, int hi, int d){if (hi lo) return;int[] count new int[R 2];key-indexed countingfor (int i lo; i hi; i )count[charAt(a[i], d) 2] ;for (int r 0; r R 1; r )count[r 1] count[r];because of recursion.for (int i lo; i hi; i )aux[count[charAt(a[i], d) 1] ] a[i];for (int i lo; i hi; i )a[i] aux[i - lo];for (int r 0; r R; r )sort R subarrays recursivelysort(a, aux, lo count[r], lo count[r 1] - 1, d 1);a[]}65Cutoff to insertion sortaux[]0b0a1a1b66MSD string sort: performanceSolution. Cutoff to insertion sort for small subarrays.Number of characters examined.・Insertion sort, but start at d・MSD examines just enough characters to sort the keys.・Number of characters examined depends on keys.・Can be sublinear in input size!thcharacter.private static void sort(String[] a, int lo, int hi, int d){for (int i lo; i hi; i )for (int j i; j lo && less(a[j], a[j-1], d); j--)exch(a, j, j-1);}・Implement less() so that it compares starting at dthcompareTo() based sortscan also be sublinear!character.private static boolean less(String v, String w, int d){for (int i d; i Math.min(v.length(), w.length()); i ){if (v.charAt(i) w.charAt(i)) return true;if (v.charAt(i) w.charAt(i)) return false;}return v.length() minedexaminedbybyMSDMSDstringstringsortsort}6768

Summary of the performance of sorting algorithmsMSD string sort vs. quicksort for stringsFrequency of operations.Disadvantages of MSD string sort.algorithmguaranteerandomextra spacestable?operations on keysinsertion sort½ N2¼ N21 compareTo()mergesortN lg NN lg NN compareTo()quicksort1.39 N lg N *1.39 N lg Nc lg N *compareTo()heapsort2 N lg N2 N lg N1compareTo()・Extra space for aux[].・Extra space for count[].・Inner loop has a lot of instructions.・Accesses memory "randomly" (cache inefficient).Disadvantage of quicksort.LSD sort†2 W (N R)2 W (N R)N R charAt()MSD sort‡2 W (N R)N log R NN DR charAt()・Linearithmic number of string compares (not linear).・Has to rescan many characters in keys with long prefix matches.doesn't rescancharacterstight inner loop,cache friendly* probabilistic† fixed-length W keysD function-call stack depth(length of longest prefix match)‡ average-length W keysGoal. Combine advantages of MSD and quicksort.6970Engineering a radix sort (American flag sort)Optimization 0. Cutoff to insertion sort.Optimization 1. Replace recursion with explicit stack.・Push subarrays to be sorted onto stack.・One count[] array now suffices.Optimization 2. Do R-way partitioning in place.・Eliminates aux[] array.・Sacrifices stability.American national flag problemDutch national flag problem5.1 S TRING S ORTS‣ strings in Java‣ key-indexed countingEngineering Radix SortPeterM. Mcllroy and Keith BosticUniversity of California at Berkeley;andM. Douglas McllroyAlgorithmsAT&T Bell LaboratoriesABSTRACT Radix sorting methods have excellentasymptotic performance on string data, for which comparison is not a unit-time operation. Attractive for usein large byte-addressable memories, these methodshave nevertheless long been eclipsed by more easilyprograÍrmed algorithms. Three ways to sort strings bybytes left to right-a stable list sort, a stable two-arraysort, and an in-place "American flag" sor¿-are illustrated with practical C programs. For heavy-duty sorting, all three perform comparably, usually running atleast twice as fast as a good quicksort. We recommendAmerican flag sort for general use.R OBERT S EDGEWICK K EVIN W AYNEhttp://algs4.cs.princeton.edu71@Computing Systems, Vol. 6. No. 1 . Winter 1993‣ LSD radix sort‣ MSD radix sort‣ 3-way radix quicksort‣ suffix arrays

3-way string quicksort (Bentley and Sedgewick, 1997)3-way string quicksort: trace of recursive callspartitioning itemOverview. Do 3-way partitioning on the dth character.・Less overhead than R-way partitioning in MSD radix sort.・Does not re-examine characters equal to the partitioning char.(but does re-examine characters not equal to the partitioning char)partitioning itemuse first character topartition into"less", "equal", and cursively sort subarrays,excluding first characterfor middle thethethetheseashellsthethethetheTrace of first few recursive calls for 3-way string quicksort (subarrays of size 1 not shown)733-way string quicksort: Java implementation743-way string quicksort vs. standard quicksortStandard quicksort.・Uses 2 N ln N string compares on average.・Costly for keys with long common prefixes (and this is a common case!)private static void sort(String[] a){ sort(a, 0, a.length - 1, 0); }private static void sort(String[] a, int lo, int hi, int d){if (hi lo) return;3-way partitioningint lt lo, gt hi;(using dth character)int v charAt(a[lo], d);int i lo 1;while (i gt)to handle variable-length strings{int t charAt(a[i], d);if(t v) exch(a, lt , i );3-way string (radix) quicksort.・Uses 2 N ln N character compares on average for random strings.・Avoids re-comparing long common prefixes.Fast Algorithms for Sorting and Searching Stringselse if (t v) exch(a, i, gt--);elsei ;Jon L. Bentley*}sort(a, lo, lt-1, d);if (v 0) sort(a, lt, gt, d 1);sort(a, gt 1, hi, d);Abstractsort 3 subarrays recursively}75We present theoretical algorithms for sorting andsearching multikey data, and derive from them practical Cimplementations for applications in which keys are character strings. The sorting algorithm blends Quicksort andradix sort; it is competitive with the best known C sortcodes. The searching alg

Digital key. Sequence of digits over fixed alphabet. Radix. Number of digits R in alphabet. Alphabets 17 604 CHAPTER 6 ! Strings holds the frequencies in Count is an example of a character-indexed array. With a Java String, we have to use an array of size 256; with Alphabet, we just need an array with one entry for each alphabet character.