Sorting in linear time (for students to read)Bucket SortBUCKET-SORT(A)Example of BUCKET-SORTAnalysis of BUCKET-SORT(A)Counting SortCOUNTING-SORT(A,B,k)Example of Counting SortAnalysis of COUNTING-SORT(A,B,k)Radix sortSlide 11Slide 12Sorting in linear time (for students to read)•Comparison sort: –Lower bound: (nlgn).•Non comparison sort:–Bucket sort, counting sort, radix sort–They are possible in linear time (under certain assumption).Bucket Sort•Assumption: uniform distribution –Input numbers are uniformly distributed in [0,1).–Suppose input size is n.•Idea:–Divide [0,1) into n equal-sized subintervals (buckets).–Distribute n numbers into buckets–Expect that each bucket contains few numbers.–Sort numbers in each bucket (insertion sort as default).–Then go through buckets in order, listing elements,BUCKET-SORT(A)1. n length[A]2. for i 1 to n3. do insert A[i] into bucket B[nA[i]]4. for i 0 to n-15. do sort bucket B[i] using insertion sort6. Concatenate bucket B[0],B[1],…,B[n-1]Example of BUCKET-SORTAnalysis of BUCKET-SORT(A)1. n length[A] (1)2. for i 1 to n O(n)3. do insert A[i] into bucket B[nA[i]] (1) (i.e. total O(n))4. for i 0 to n-1 O(n)5. do sort bucket B[i] with insertion sort O(ni2) (i=0n-1 O(ni2))6. Concatenate bucket B[0],B[1],…,B[n-1] O(n)Where ni is the size of bucket B[i].Thus T(n) = (n) + i=0n-1 O(ni2) = (n) + nO(2-1/n) = (n). Beat (nlg n)Counting Sort•Assumption: n input numbers are integers in range [0,k], k=O(n). •Idea: –Determine the number of elements less than x, for each input x.–Place x directly in its position.COUNTING-SORT(A,B,k )1. for i0 to k2. do C[i] 0 3. for j 1 to length[A]4. do C[A[j]] C[A[j]]+15. // C[i] contains number of elements equal to i.6. for i 1 to k7. do C[i]=C[i]+C[i-1]8. // C[i] contains number of elements i.9. for j length[A] downto 110. do B[C[A[j]]] A[j]11. C[A[j]] C[A[j]]-1Example of Counting SortAnalysis of COUNTING-SORT(A,B,k)1. for i0 to k (k)2. do C[i] 0 (1)3. for j 1 to length[A] (n)4. do C[A[j ]] C[A[j]]+1 (1) ((1) (n)= (n))5. // C[i] contains number of elements equal to i. (0)6. for i 1 to k (k)7. do C[i]=C[i]+C[i-1] (1) ((1) (n)= (n))8. // C[i] contains number of elements i. (0)9. for j length[A] downto 1 (n)10. do B[C[A[j]]] A[j] (1) ((1) (n)= (n))11. C[A[j]] C[A[j]]-1 (1) ((1) (n)= (n))Total cost is (k+n), suppose k=O(n), then total cost is (n). Beat (nlg n).Radix sort•Suppose a group of people, with last name, middle, and first name (each has one letter).•For example: (z, x, k), (z,j,y), (f,s,f), …•Sort it by the last name, then by middle, finally by the first name•Solution 1: –sort by last name first as into (possible) 26 bins, –Sort each bin by middle name into (possible) 26 more bins (26*26 =512) –Sort each of 512 bins by the first name into 26 bins•So if many names, there may need possible 26*26*26 bins.•Suppose there are n names, there need possible n bins. What is the efficient solution?Radix sort•By first name, then middle, finally last name.•Then after every pass of sort, the bins can be combined as one file and proceed to the next sort.•Radix-sort(A,d)–For i=1 to d do•use a stable sort to sort array A on digit i.•Lemma 8.3: Given n d-digit numbers in which each digit can take on up to k possible values, Radix-sort correctly sorts these numbers in (d(n+k )) time. •If d is constant and k=O(n), then time is
View Full Document