New version page

# IUPUI CS 580 - Sorting in linear time

Pages: 12
Documents in this Course

9 pages

12 pages

24 pages

17 pages

37 pages

58 pages

11 pages

15 pages

9 pages

13 pages

Unformatted text preview:

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 i0 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 i0 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