DOC PREVIEW
BU CS 333 - linear sorts

This preview shows page 1-2-23-24 out of 24 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 24 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 24 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 24 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 24 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 24 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Linear SortsLinear SortsCounting sortSlide 4Counting SortSlide 6Slide 7Slide 8Analysis:Bucket sortSlide 11AnalysisHow did IBM get rich originally?A punched cardCard punching machineHollerith’s tabulating machinesCard sorting machineRadix sortSlide 19Radix sort- with decimal digitsRadix sort with unstable digit sortIs Quicksort stable?Is Heapsort stable?ExampleLinear SortsCounting sortBucket sortRadix sortLinear Sorts 2Linear Sorts •We will study algorithms that do not depend only on comparing whole keys to be sorted.•Counting sort•Bucket sort•Radix sortLinear Sorts 3Counting sort•Assumptions:–n records–Each record contains keys and data–All keys are in the range of 1 to k•Space–The unsorted list is stored in A, the sorted list will be stored in an additional array B–Uses an additional array C of size kLinear Sorts 4Counting sort•Main idea: 1. For each key value i, i = 1,…,k, count the number of times the keys occurs in the unsorted input array A. Store results in an auxiliary array, C 2. Use these counts to compute the offset. Offseti is used to calculate the location where the record with key value i will be stored in the sorted output list B. The offseti value has the location where the last keyi .•When would you use counting sort?•How much memory is needed?Linear Sorts 5Counting SortCounting-Sort( A, B, k)1. for i  1 to k2. do C[i ]  03. for j  1 to length[A]4. do C[A[ j ] ]  C[A[ j ] ] + 15. for i  2 to k6. do C[i ]  C[i ] +C[i -1]7. for j  length[A] down 18. do B [ C[A[ j ] ] ]  A[ j ] 9. C[A[ j ] ] ]  C [A[ j ] ] -1Analysis:Input: A [ 1 .. n ],A[J]  {1,2, . . . , k }Output: B [ 1 .. n ], sortedUses C [ 1 .. k ],auxiliary storageAdapted from Cormen,Leiserson,RivestLinear Sorts 6A4 31 4 431 2 3 4 5 6k = 4, length = 6Cafter lines 1-20 0 0 0Cafter lines 3-41 0 2 3Counting-Sort( A, B, k)1. for i  1 to k2. do C[i ]  03. for j  1 to length[A]4. do C[A[ j ] ]  C[A[ j ] ] + 15. for i  2 to k6. do C[i ]  C[i ] +C[i -1]Cafter lines 5-61 1 3 6Linear Sorts 77. for j  length[A] down 18. do B [ C[A[ j ] ] ]  A[ j ] 9. C[A[ j ] ] ]  C [A[ j ] ] -1A4 31 4 431 2 3 4 5 6B1 2 3 4 5 6C1 1 3 6<-1-><- - 3 - -><- - - 4 - ->Linear Sorts 8Counting sort3 Clinton4 Smith1 Xu2 Adams3 Dunn4 Yi 2 Baum1 Fu3 Gold1 Lu1 Land12340000123442321234(4)(3)26(9)8111 Lu1 Land3 Gold1234567891011Original listBC C C1234567891011finalcounts"offsets"ASort bucketsLinear Sorts 9Analysis:•O(k + n) time –What if k = O(n)•But Sorting takes  (n lg n) ????•Requires k + n extra storage.•This is a stable sort: It preserves the original order of equal keys.•Clearly no good for sorting 32 bit values.Linear Sorts 10Bucket sort•Keys are distributed uniformly in interval [0, 1)•The records are distributed into n buckets•The buckets are sorted using one of the well known sorts•Finally the buckets are combinedLinear Sorts 11Bucket sort.78.17.39.26.72.94.21.12.23.68123456789100123456789////.12 .17/ .23 .68/ .72 .94/ .39/ .78/ .21 .26/ Step 1 distribute0123456789////.12 .17/ .21 .68/ .72 .94/ .39/ .78/ .23 .26/ Step 2 sortedStep3 combineLinear Sorts 12Analysis•P = 1/n , probability that the key goes to bucket i.•Expected size of bucket is np = n  1/n = 1•The expected time to sort one bucket is (1).•Overall expected time is  (n).Linear Sorts 13How did IBM get rich originally?•In the early 1900's IBM produced punched card readers for census tabulation.•Cards are 80 columns with 12 places for punches per column. Only 10 places needed for decimals.–Picture of punch card.•Sorters had 12 bins. •Key idea: sort the least significant digit first.Linear Sorts 14A punched cardLinear Sorts 15Card punching machineIBM card punching machineLinear Sorts 16Hollerith’s tabulating machines•As the cards were fed through a "tabulating machine," pins passed through the positions where holes were punched completing an electrical circuit and subsequently registered a value. •The 1880 census in the U.S. took seven years to complete•With Hollerith's "tabulating machines" the 1890 census took the Census Bureau six weeksLinear Sorts 17Card sorting machineIBM’s card sorting machineLinear Sorts 18Radix sort•Main idea–Break key into “digit” representation key = id, id-1, …, i2, i1–"digit" can be a number in any base, a character, etc•Radix sort:for i= 1 to d sort “digit” i using a stable sort •Analysis : (d  (stable sort time)) where d is the number of “digit”sLinear Sorts 19Radix sort•Which stable sort?–Since the range of values of a digit is small the best stable sort to use is Counting Sort.–When counting sort is used the time complexity is (d  (n +k )) where k is the range of a "digit".•When k  O(n), (d  n)Linear Sorts 20Radix sort- with decimal digits17813932657229432191036812345678910321572294326178368139910321326139368572178294139178294321326368572910Input listSorted listLinear Sorts 21Radix sort with unstable digit sort17131213171713 Input listList not sortedSince unstableand both keys equal to 1Linear Sorts 22Is Quicksort stable? •Note that data is sorted by key•Since sort unstable cannot be used for radix sort515548123485551 Key DataAfter partitionof 0 to 2After partitionof 1 to 2485551Linear Sorts 23Is Heapsort stable? •Note that data is sorted by key•Since sort unstable cannot be used for radix sort515512Key DataComplete binarytree, and max heap51555551HeapSortedAfterswapLinear Sorts 24ExampleSort 1 million 64-bit numbers.We could use an in place comparison sort which would run in (n lg n) in the average case. lg 1,000,000  20 passes over the dataWe can treat a 64 bit number as a 4 digit, radix-216 number. So d = 4, k = 216 , n = 1,000,000 (d (n + k )) =  ( 4(216 +n)). This takes 4 * 2 passes over the data.16 bitsd316 bitsd216 bitsd116 bitsdo64 bits number = d3*(216)3 + d2*(216)2+ d1 (216)1 + d0(216)0 Adapted from


View Full Document

BU CS 333 - linear sorts

Download linear sorts
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view linear sorts and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view linear sorts 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?