CISC320, F05, Lec6, Liao 1CISC 320 Introduction to AlgorithmsFall 2005Lecture 6Sorting in linear timeCISC320, F05, Lec6, Liao2A job interview question:Given integers 1 to 100, but in an arbitrarily unsorted order. How fast can these 100 integers be sorted into the increasing order?Given 10 integers valued between 1 and 100, and in an arbitrarily unsorted order. How fast can these 10 integers be sorted into the increasing order?Given 10,000 integers valued between 1 and 100,and in an arbitrarily unsorted order. How fast can they be sorted into the increasing order?CISC320, F05, Lec6, Liao3Counting sort: ideas Problem: to sort an array A of integers Extra info: each of the n input elements of A is an integer in the range [0, k]. One scan through A will find how many times each integer i ∈[0,k] appears in A. The counts are stored in an auxiliary array C[0..k]. Thus element C[i] is the number of times that integer i appears in A. ∑j=0 to iC[i] gives the number of elements of A that are less than i, and this tells where to put i in a sorted array.CISC320, F05, Lec6, Liao4Counting sort: algorithmCounting-sort (A, B, k)1. for (i=0; i<k; i++) 2. C[i] = 0; // initialize array C to store counts.3. for (j=0; j<n; j++)4. C[A[j]] = C[A[j]] + 1; // scan A and count.5. for (I = 1, i<k, i++)6. C[i] = C[i] + C[i-1]; // transform to cumulative counts7. for (j = n; j > 1; j--) 8. B[C[A[j]]] = A[j]; // sort to the right place9. C[A[j]] = C[A[j]] – 1; // update the countCISC320, F05, Lec6, Liao5Counting sort: example2 5 3 0 2 3 0 31 2 3 4 5 6 7 8A2 0 2 3 0 1 0 1 2 3 4 5 C2 2 4 7 7 8 C0 1 2 3 4 5 2 5 3 0 2 3 0 31 2 3 4 5 6 7 8A2 2 4 7 7 8 0 1 2 3 4 5 C3 1 2 3 4 5 6 7 8B3j2 5 3 0 2 3 0 31 2 3 4 5 6 7 8A2 2 4 6 7 8 0 1 2 3 4 5 C3 1 2 3 4 5 6 7 8B3j02 5 3 0 2 3 0 31 2 3 4 5 6 7 8A1 2 4 6 7 8 0 1 2 3 4 5 C3 1 2 3 4 5 6 7 8B3j0 3(a)(b)(c)(d)(e)CISC320, F05, Lec6, Liao6Counting sort: complexity analysis TimeΘ(k) + Θ(n) + Θ(k) + Θ(n) ∈ Θ(k + n)  Space: Θ(k+n) not in-placeNote: 1. Counting sort is not comparison based sorting. Instead, it uses the actual values of the elements to index into an array. Thus, its linear performance breaks the Ω(n log n) lower bound for comparison based sorting problems.2. Stable sortInitialize array CScan A and Count Transform CScan A and sortCISC320, F05, Lec6, Liao7Radix sort: ideas Problem: to sort A, an array of nd-digit numbers Strategy: sort numbers based on their least significant digit, then on their second least significant digit, so on and so forth, until sort on their most significant digit is done.CISC320, F05, Lec6, Liao8Radix sort: an example329457657839436720355720355436457657329839720329436839355457657329355436457657720839unsorted ones tens hundredsCorrectness: Induction on digit positionAssume numbers are sorted up to the i-th digit. When sort on (i+1) –th digit:1) Two numbers that differ in the (i+1)-th digit are correctly sorted.2) Two numbers having same (i+1)-th digit remain the same order up to i-th digit, because sorting on each digit is stable.CISC320, F05, Lec6, Liao9Radix sort:  Why not sort from most significant digits to less significant digits?1 34 24 21 3CISC320, F05, Lec6, Liao10Radix sort: analysisTime = (number of digits) x (time for sorting on each digit)= d x Θ(10+n) ∈O(n)note: counting sort is utilized for sorting on each digit.Exercise: Show how to sort n integers in the range 1 to n2 -1 in O(n) time.CISC320, F05, Lec6, Liao11Pancake sorting?Bounds for sorting by prefix reversal.Gates, William H. and Christos H. Papadimitriou.Discrete Mathematics 27, 47--57, 1979The authors study the problem of sorting a sequence of distinctnumbers by prefix reversal -- reversing a subsequence of adjacentnumbers which always contains the first number of the currentsequence. Let f(n) denote the smallest number of prefix reversalswhich is sufficient to sort n numbers in any ordering. The authorsprove that f(n) <= (5n+5)/3 by demonstrating an algorithm which neverneeds more prefix reversals. They also prove that f(n) >= 17n/16whenever n is a multiple of 16. The sequences which achieve this boundare periodic extensions of the basic sequence 1, 7, 5, 3, 6, 4, 2, 8,16, 10, 12, 14, 11, 13, 15, 9. If, furthermore, each integer isrequired to participate in an even number of prefix reversals, thecorresponding function g(n) is shown to satisfy 3n/2 - 1 <= g(n) <=2n+3.CISC320, F05, Lec6,