【文档说明】计算机算法导论_第8章课件.ppt，共(58)页，1.891 MB，由小橙橙上传

转载请保留链接：https://www.ichengzhen.cn/view-77476.html

以下为本文档部分文字说明：

计算机算法导论_第8章课件SortingandOrderStatistics•IntroductionSortingproblemDefinition:Input:Asequence<a1,a2,…,an>ofnumbers.Output:Apermuta

tion<a'1,a'2,…,a'n>,suchthata'1≤a'2≤…≤a'n.ThestructureofthedataDefinition:Record=key+satellitedataAssumption:

TheinputconsistsonlyofnumbersWhysorting?1.Theneedinherentinanapplication2.Algorithmsoftenusesortingasakeysubroutine3.Awidevarietyofsorti

ngalgorithms,arichsetoftechniques4.Aproblemcanbeprovedanontriviallowerbound.5.Manyengineeringissuescometoforewhenimplementingsortingalgori

thms.Sortingalgorithms1.Ain-placesortingalgorithm2.Comparisonsort3.Thecountingsortalgorithm4.Theradixsortalgorithm5.Thebucke

tsortalgorithmOrderstatisticsTheithorderstatisticofasetofnnumbersistheithsmallestnumberintheset.8、Sortinginlineartime8.1LowerboundsforsortingAs

sumption:1.Alloftheinputelementsaredistinct2.Allcomparisonshavetheformai≤ajHowfastcanwesort?Allthesortingal

gorithmswehaveseensofararecomparisonsorts:onlyusecomparisonstodeterminetherelativeorderofelements.•E.g.,insertionsort,mergesort,quicksort,heaps

ort.Thebestworst-caserunningtimethatwe’veseenforcomparisonsortingisO(nlgn).IsO(nlgn)thebestwecando?Decisiontreescanhelpusansw

erthisquestion.••••••••••Decision-treemodelAdecisiontreecanmodeltheexecutionofanycomparisonsort:•Onetree

foreachinputsizen.•Viewthealgorithmassplittingwheneveritcomparestwoelements.•Thetreecontainsthecomparisonsalongallpossibleinstructiontraces.

•Therunningtimeofthealgorithm=thelengthofthepathtaken.•Worst-caserunningtime=heightoftree.Lowerboundfordecisi

on-treesortingLowerboundforcomparisonsortingCorollary.Heapsortandmergesortareasymptoticallyoptimalcomparisonsortingalgorithms.8.

2CountingsortSortinginlineartimeCountingsort:Nocomparisonsbetweenelements.•Input:A[1..n],whereA[j]∈{1,2,…,k}.•Output:B[1..n],sorted.•

Auxiliarystorage:C[1..k].Countingsortfori←1tokdoC[i]←0forj←1tondoC[A[j]]←C[A[j]]+1⊳C[i]=|{key=i}|fori←2tokdoC[i]←C[i]+C[i–1]⊳C[i

]=|{key≤i}|forj←ndownto1doB[C[A[j]]]←A[j]C[A[j]]←C[A[j]]–1••••••••••••••••••••••••••••••••RunningtimeIfk=O(n),thencountingsorttakesΘ(n)time.•But

,sortingtakesΩ(nlgn)time!•Where’sthefallacy?Answer:•ComparisonsortingtakesΩ(nlgn)time.•Countingsortisn

otacomparisonsort.•Infact,notasinglecomparisonbetweenelementsoccurs!••8.3Radixsort•Origin:HermanHollerith’scard-sor

tingmachineforthe1890U.S.Census.(SeeAppendix.)•Digit-by-digitsort.•Hollerith’soriginal(bad)idea:sortonmost-significantdi

gitfirst.•Goodidea:Sortonleast-significantdigitfirstwithauxiliarystablesort.••••••••••••••••8.4BucketsortAssump

tion:Theinputisdrawnfromauniformdistribution.IdeaAlgorithmCorrectnessAnalysisAnalysisAnalysisAnalysisAnaly

sisConclusion