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

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

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

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

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

tsonlyofnumbersWhysorting?1.Theneedinherentinanapplication2.Algorithmsoftenusesortingasakeysubroutine3.Awid

evarietyofsortingalgorithms,arichsetoftechniques4.Aproblemcanbeprovedanontriviallowerbound.5.Manyengineeringissuescometoforewhenimplementingsortin

galgorithms.Sortingalgorithms1.Ain-placesortingalgorithm2.Comparisonsort3.Thecountingsortalgorithm4.Theradixsortalgorithm5.Th

ebucketsortalgorithmOrderstatisticsTheithorderstatisticofasetofnnumbersistheithsmallestnumberintheset

.8、Sortinginlineartime8.1LowerboundsforsortingAssumption:1.Alloftheinputelementsaredistinct2.Allcomparisonshavetheformai≤ajHowfastcanwes

ort?Allthesortingalgorithmswehaveseensofararecomparisonsorts:onlyusecomparisonstodeterminetherelativeorderofelements.•E.g.,

insertionsort,mergesort,quicksort,heapsort.Thebestworst-caserunningtimethatwe’veseenforcomparisonsortingisO(

nlgn).IsO(nlgn)thebestwecando?Decisiontreescanhelpusanswerthisquestion.••••••••••Decision-treemodelAdecisiontreecanmodeltheexecution

ofanycomparisonsort:•Onetreeforeachinputsizen.•Viewthealgorithmassplittingwheneveritcomparestwoelements.•Thetre

econtainsthecomparisonsalongallpossibleinstructiontraces.•Therunningtimeofthealgorithm=thelengthofthep

athtaken.•Worst-caserunningtime=heightoftree.Lowerboundfordecision-treesortingLowerboundforcomparisonsortingCorollary.Heapsortandmerge

sortareasymptoticallyoptimalcomparisonsortingalgorithms.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.•Countingsortisnotacomparisonsort.•Infact,notasinglecompariso

nbetweenelementsoccurs!••8.3Radixsort•Origin:HermanHollerith’scard-sortingmachineforthe1890U.S.Census.(SeeAppendix.)•Digit-by-digitsort.•Hollerith

’soriginal(bad)idea:sortonmost-significantdigitfirst.•Goodidea:Sortonleast-significantdigitfirstwithaux

iliarystablesort.••••••••••••••••8.4BucketsortAssumption:Theinputisdrawnfromauniformdistribution.IdeaAlgorithmCorrectnes

sAnalysisAnalysisAnalysisAnalysisAnalysisConclusion