T&RTeamofAlgorithmDesignCollegeofComputerScienceandEngineering,CQUAlgorithmAnalysis&Design

IntroductiontoAlgorithmChapter8:LinearSortOutline8.1Howfastcanwesort?8.2CountingSort8.3RadixSort8.2BucketSort8.1Howfastcanwesort?Howfastcanwesort?Allthesortingalgorithmswehaveseensofararecomparisonsorts:usecomparisonstodeterminetherelativeorderofelements.E.g.,mergesort,quicksort,heapsort.Thebestworst-caserunningtimethatwe’veseenforcomparisonsortisO(n

logn).Actually,thisisindeedthebestworst-caserunningtimeofcomparisonsort.Decision-treeexampleSort<a1,a2,a3>Eachinternalnodeislabeledi:jfori,j∈{1,2,3}Theleftsub-treeshowssubsequentcomparisonswithai≤ajTherightsub-treeshowsubsequentcomparisonswithai>aj≤≤≤≤≤>>>>>Decision-treeexampleSort<a1,a2,a3>=

<9,4,6>Eachinternalnodeislabeledi:jfori,j∈{1,2,3}Theleftsub-treeshowssubsequentcomparisonswithai≤ajTherightsub-treeshowsubsequentcomparisonswithai>ajEachLeafdenotesapermutationoftheto-be-sortedarray≤≤≤≤≤>>>>>Decision-treeexampleSort<a1,a2,a3>=

<9,4,6>Eachinternalnodeislabeledi:jfori,j∈{1,2,3}Theleftsub-treeshowssubsequentcomparisonswithai≤ajTherightsub-treeshowsubsequentcomparisonswithai>ajEachLeafdenotesapermutationoftheto-be-sortedarray≤≤≤≤≤9>4>>>>Decision-treeexampleSort<a1,a2,a3>=

<9,4,6>Eachinternalnodeislabeledi:jfori,j∈{1,2,3}Theleftsub-treeshowssubsequentcomparisonswithai≤ajTherightsub-treeshowsubsequentcomparisonswithai>ajEachLeafdenotesapermutationoftheto-be-sortedarray≤≤≤≤≤9>4>>>9>6Decision-treeexampleSort<a1,a2,a3>=

<9,4,6>Eachinternalnodeislabeledi:jfori,j∈{1,2,3}Theleftsub-treeshowssubsequentcomparisonswithai≤ajTherightsub-treeshowsubsequentcomparisonswithai>ajEachLeafdenotesapermutationoftheto-be-sortedarray≤≤≤≤9>4>>>9>64≤6Decision-treeexampleSort<a1,a2,a3>=

<9,4,6>Eachinternalnodeislabeledi:jfori,j∈{1,2,3}Theleftsub-treeshowssubsequentcomparisonswithai≤ajTherightsub-treeshowsubsequentcomparisonswithai>ajEachLeafdenotesapermutationoftheto-be-sortedarray≤≤≤≤>>>9>49>64≤6Decision-treeexampleSort<a1,a2,a3>=

<9,4,6>Thetreecontainsthecomparisonsalongallpossiblepaths.Therunningtimeofthealgorithm=thelengthofthepathtaken.TheWorst-caserunningtime=theheightofthetree.≤≤≤≤>>>9>49>64≤6LowerBoundforComparisonSortingTheorem.AnycomparisonsortingalgorithmrequiresΩ(n

logn)comparisonsintheworstcaseProof:Worst-casedictatedbytreeheighthAnn-element-arrayhaven!differentpermutationsWeneedatlestoneleaftodenoteonepermutationThus,thelowerboundofh

canbedenotedby:h≥log(n!)≥log(n/e)n=nlogn-nloge=Ω(nlogn)Stirling’sApproximationHeapsortandmergesortareasymptoticallyoptimalcomparisonsortingalgorithms.CanWeSortFaster?Isthereafasteralgorithm?Canwesortinlineartime?HOW?8.2CountingSortCountingSortCountingsort:sortwithoutcomparisonInput:A[1..n],whereA[j]∈{1,2,…,k}Output:sortedarrayB[1..n]Auxiliarystorage:C[1..k]P.S.:NotethatthesizeoftheauxiliaryarrayisdecidedbythelargestelementinA.CountingSortForeachelementx

inA,ifthereare17elementslessthanxinA,thenx

deservetheoutputposition18.WhatifmultipleelementsequaltoxinA?Putthe1stinposition18,2ndinposition19,3rdinposition20,etc.Whatifthereare17elementsnotgreaterthanxinA?Putthelast

inposition17,thesecond-last

inposition16,etc.CountingSortPseudoCodeCounting-sortexample4134312345A:1234C:12345B:n=5,k=4Counting-sortexample4134312345A:1234C:12345B:Counting-sortexample4134312345A:00001234C:12345B:Counting-sortexample4134312345A:00001234C:12345B:Counting-sortexample03431412345A:10001234C:12345B:Counting-sortexample0113431412345A:001234C:12345B:Counting-sortexample01113431412345A:01234C:12345B:Counting-sortexample11123431412345A:01234C:12345B:Counting-sortexample21123431412345A:01234C:12345B:Counting-sortexample21123431412345A:01234C:12345B:Counting-sortexample022103431412345A:1234C:12345B:Counting-sortexample022113431412345A:1234C:12345B:Counting-sortexample122133431412345A:1234C:12345B:Counting-sortexample123153431412345A:1234C:12345B:Counting-sortexample51133431412345A:11234C:12345B:Counting-sortexample51133431412345A:11234C:12345B:Counting-sortexample333513431412345A:11234C:12345B:Counting-sortexample332513431412345A:11234C:12345B:Counting-sortexample51123431412345A:11234C:312345B:Counting-sortexample5342513431412345A:11234C:12345B:Counting-sortexample5434213431412345A:11234C:12345B:Counting-sortexample41123431412345A:11234C:4312345B:Counting-sortexample44332213431412345A:11234C:12345B:Counting-sortexample44332113431412345A:11234C:12345B:Counting-sortexample41113431412345A:11234C:43312345B:Counting-sortexample134431113431412345A:11234C:12345B:Counting-sortexample103443113431412345A:11234C:12345B:Counting-sortexample41013431412345A:11234C:433112345B:Counting-sortexample1034434143431412345A:11234C:12345B:Counting-sortexample4310343413431412345A:11234C:12345B:Counting-sortexample31013431412345A:11234C:4433112345B:AnalyzingCountingSortTheoveralltimeisO(k+n)50O(k)O(n)O(k)O(n)RunningtimeofCountingSortIfk=O(n),thencountingsorttakesO(n)time.However,comparisonsorttakeΩ(n

logn)time!Whatenablesthislinearimplementation?CountingsortisnotacomparisonsortOr,singlecomparisonsbetweenelementsneveroccurs51StabilityofCountingSortCountingsortisstable:itreservestheinputorderamongequalelements.Exercise:whatisthelimitationofcountingsort?528.3RadixSortRadixSortOrigin:HermanHollerith’scard-sortingmachineforthe1890U.S.CensusThe1880U.S.Censustookalmost

10yearstoprocess.WhilealectureratMIT,Hollerith

prototypedpunched-cardtechnology.Hismachines,includinga“cardsorter”,

allowedthe1890censustotaltobe

reportedin6weeks.HefoundedtheTabulatingMachine

Companyin1911,whichmerged

withothercompaniesin1924

toformIBM.54OperationofRadixSort559779605977960534684732553325734463825355230567799StablesortOperationofRadixSort5697796059779605346847325533257344638253552305677992535523734834622335550969577StablesortStablesortOperationofRadixSort57977960597796053468473255332573446382535523056779925355237348346223355509695777348346334467825355239567709StablesortStablesortStablesortCorrectnessofRadixSort587348346223355509695773344678253552395677091.Basedontheinductionon

digitposition.2.Assumethatthenumbersaresortedbytheirlow-ordert–1digits.3.Andthensortondigitt.StablesortCorrectnessofRadixSort59734834622335550969577334467825355239567709StablesortTwonumbersthatdifferindigittarecorrectlysorted.1.Basedontheinductionon

digitposition.2.Assumethatthenumbersaresortedbytheirlow-ordert–1digits.3.Andthensortondigitt.CorrectnessofRadixSort60734834622335550969577334467825355239567709StablesortTwonumbersequalindigittareputinthesameorderastheinput:correctorder1.Basedontheinductionon

digitposition.2.Assumethatthenumbersaresortedbytheirlow-ordert–1digits.3.Andthensortondigitt.AnalyzingRadixSortO(d

T(n))whereT(n)denotestherunningtimeoftheinnersort.Ifweusecountingsortastheinnersortanddisconstant,thenradixsortcanachieveO(n)LSD:sortnumbersontheirLeastSignificantDigitfirst.RADIX-SORTRADIX-SORT(A,d)1

for

i

←1

to

d2do

useastablesorttosortarrayAondigit

i8.4BucketSortBucketSortSimilartocountingsort,bucketsortisfastbecauseofaninitialhypothesisDifferentintuitivehypothesis.CountingSort:theinputconsistofintegersinasmallrangeBucketSort:theinputkeeptoauniformdistributionGeneralIdea:dividetheinterval[0,1)intonequal-sizedsubintervalswhichformtheso-calledbuckets,andthendistributetheninputnumberintothebuckets.63BucketSortAssumethatalltheinputisgeneratedbyarandomprocessthatdistributeselementsuniformovertheinterval[0,1)Applybucketsort:①Allocateabucketforeachvalueofthekey>>Thatis,insertA[i]intolistB[?n

A[i]?]②Foreachbucket>>sortlistB[i]withinsertionsort③concatenatethelistB[0],B[1],…,B[n-1]togetherinorder64BucketSortPseudoCode650BucketSortExample(a)TheinputarrayA[1..10](b)ThearrayB[0..9]ofsortedlists(b