CS245-2014S-12 Non-Comparison Sorts 112-0: Comparison Sorting• Comparison sorts work by comparing elements• Can on ly compare 2 elements at a time• Check for <, >, =.• All the sorts we have seen so far (Insertion, Quick, Merge, Heap, etc.) are comparison sorts• If we know nothing about the list to b e sorted, we need to use a comparison sort12-1: Decision Trees Insertion Sort on list {a, b, c}a<b<c b<c<aa<c<b c<a<bb<a<c c<b<aa<b<ca<c<bc<a<bb<a<cb<c<ac<b<aa<b<c a<c<bc<a<ba<c<bc<a<bb<a<cb<c<ac<b<ab<c<a c<b<aa<bb<ab<c c<ba<c c<aa<cc<a b<c c<b12-2: Decision Trees• Every comparison sorting algorithm ha s a dec isio n tree• What is the best-case number of com parisons for a comparison sorting algorithm, given the decision tre e for thealgorithm ?12-3: Decision Trees• Every comparison sorting algorithm ha s a dec isio n tree• What is the best-case number of com parisons for a comparison sorting algorithm, given the decision tre e for thealgorithm ?• (The depth of the shallowest leaf) + 1• What is the worst ca se number of comparisons for a compar ison sorting algo rithm, given the decision tree forthe algorith m?12-4: Decision Trees• Every comparison sorting algorithm ha s a dec isio n tree• What is the best-case number of com parisons for a comparison sorting algorithm, given the decision tre e for thealgorithm ?• (The depth of the shallowest leaf) + 1CS245-2014S-12 Non-Comparison Sorts 2• What is the worst ca se number of comparisons for a compar ison sorting algo rithm, given the decision tree forthe algorith m?• The height o f the tree – (depth of the deepest leaf) + 112-5: Decision Trees• What is the largest number of nodes for a tree of depth d?12-6: Decision Trees• What is the largest number of nodes for a tree of depth d?• 2d• What is the minimum height, for a tree that has n leaves?12-7: Decision Trees• What is the largest number of nodes for a tree of depth d?• 2d• What is the minimum height, for a tree that has n leaves?• lg n• How many leaves are there in a decision tree for sorting n elements?12-8: Decision Trees• What is the largest number of nodes for a tree of depth d?• 2d• What is the minimum height, for a tree that has n leaves?• lg n• How many leaves are there in a decision tree for sorting n elements?• n!• What is the minimum height, for a de c isio n tree for sorting n elements?12-9: Decision Trees• What is the largest number of nodes for a tree of depth d?• 2d• What is the minimum height, for a tree that has n leaves?• lg n• How many leaves are there in a decision tree for sorting n elements?• n!• What is the minimum height, for a de c isio n tree for sorting n elements?CS245-2014S-12 Non-Comparison Sorts 3• lg n!12-10: lg (n!) ∈ Ω(n lg n)lg(n!) = lg(n ∗ (n − 1) ∗ (n − 2) ∗ . . . ∗ 2 ∗ 1)= (lg n) + (lg(n − 1)) + (lg(n − 2)) + . . .+(lg 2) + (lg 1)≥ (lg n) + (lg(n − 1)) + . . . + (lg(n/2))|{z }n/2 terms≥ (lg n/2) + (lg(n/2)) + . . . + lg(n/2)|{z }n/2 terms= (n/2) lg(n/2)∈ Ω(n lg n)12-11: Sorting Lower Bound• All comparison sorting algorithms can be represented by a decision tree with n! leaves• Worst-case number of comp arisons required b y a sorting algorithm represented by a decision tree is the heightof the tree• A decision tree with n! leaves must have a height of at least n lg n• All comparison sorting algorithms have worst-case runnin g time Ω(n lg n)12-12: Counting Sort• Sorting a list of n integers• We know all integers are in the rang e 0 . . . m• We can potentially sort the integers faster than n lg n• Keep track of a “Coun te r Arra y” C:• C[i] = # of tim es value i appears in the listExample: 3 1 3 5 2 1 6 7 8 11 2 3 4 5 6 7 8 912-13: Counting Sort Example1 2 3 4 5 6 7 8 931352167810 0 0 0 0 0 0 0 000CS245-2014S-12 Non-Comparison Sorts 412-14: Counting Sort Example1 2 3 4 5 6 7 8 9 1352167810 0 0 1 0 0 0 0 00012-15: Counting Sort Example1 2 3 4 5 6 7 8 9 352167810 1 0 1 0 0 0 0 00012-16: Counting Sort Example1 2 3 4 5 6 7 8 9 52167810 1 0 2 0 0 0 0 00012-17: Counting Sort Example1 2 3 4 5 6 7 8 9 2167810 1 0 2 0 1 0 0 00012-18: Counting Sort Example1 2 3 4 5 6 7 8 9 167810 1 1 2 0 1 0 0 00012-19: Counting Sort Example1 2 3 4 5 6 7 8 9 67810 2 1 2 0 1 0 0 00012-20: Counting Sort ExampleCS245-2014S-12 Non-Comparison Sorts 51 2 3 4 5 6 7 8 9 7810 2 1 2 0 1 1 0 00012-21: Counting Sort Example1 2 3 4 5 6 7 8 9 810 2 1 2 0 1 1 1 00012-22: Counting Sort Example1 2 3 4 5 6 7 8 9 10 2 1 2 0 1 1 1 10012-23: Counting Sort Example1 2 3 4 5 6 7 8 9 0 3 1 2 0 1 1 1 10012-24: Counting Sort Example1 2 3 4 5 6 7 8 9 0 3 1 2 0 1 1 1 1001 1 1 2 3 3 5 6 7 8 12-25: Θ() of Counting Sort• What its the running time of Counting Sort?• If the list has n elements, all of which are in the range 0 . . . m:12-26: Θ() of Counting Sort• What its the running time of Counting Sort?• If the list has n elements, all of which are in the range 0 . . . m:• Running time is Θ(n + m)• What about the Ω(n lg n) bound for all sorting algorithms?CS245-2014S-12 Non-Comparison Sorts 612-27: Θ() of Counting Sort• What its the running time of Counting Sort?• If the list has n elements, all of which are in the range 0 . . . m:• Running time is Θ(n + m)• What about the Ω(n lg n) bound for all sorting algorithms?• For Comparison Sorts, which allow for sorting arb itrary data. What happens when m is very large?12-28: Binsort• Counting Sort will need some modification to allow us to sort records with integer keys, instead of just integers.• Binsort is much like Counting Sort, except that in each index i of the counting array C:• Instead of storing the number o f elements with the value i, we store a list of all elements with the value i.12-29: Binsort Example1 2 3 4 5 6 7 8 9/ / / / / / / / /0/3 1 2 6 2 4 5 3 9 7 keydatamark john mary sue julie rachel pixel shadow alex james12-30: Binsort Example1 2 3 4 5 6 7 8 9/ /03 1 2 6 2 4 5 3 9 7 keydatamark john …