ADA分治法快速排序

2023/2/51ReviewoflastclassDivideandConquertechniqueThemergesortalgorithmanditsbest-case,worst-caseandaverage-caseanalysis2023/2/52DivideAndConquer(II)Chapter4ApplicationtosortingproblemQuicksort2023/2/53GoalsoftheLectureAttheendofthislecture,youshouldMastertheideaofquicksortalgorithmMasterthebest-case,worst-caseandaverage-caseanalysisofquicksortalgorithmUnderstandthedifferencebetweenmergesortandquicksort2023/2/54QuicksortAnothersortalgorithmexampletorevealtheessenceofdivide-and-conquertechniqueItsideacanbedescribedasfollows:Divide:PartitionthearrayA[p..r]intotwosubarraysA[p..q]andA[q+1..r]Invariant:AllelementsinA[p..q]arelessthanallelementsinA[q+1..r]Conquer:SortthetwosubarraysrecursivelyMerge:Unlikemergesort,nocombiningstep,twosubarraysformanalready-sortedarray2023/2/55QuicksortAlgorithmALGORITHMQuickSort(A,l,r)

//Sortsasubarraybyquicksort //Input:AsubarrayA[l…r]ofA[0…n-1],definedbyits // leftandrightindiceslandr //Output:SubarrayA[l…r]sortedinnondecreasingorder

if

l<r

s

←Partition(A,l,r)//sisasplitposition QuickSort(A,l,s-1) QuickSort(A,s+1,r)

end

if2023/2/56Clearly,alltheactiontakesplaceinthedivide

stepshouldbethefollowings:SelectapivotandrearrangesthearrayinplaceEndresult:TwosubarraysbeenseparatedbythepivotTheelementsinonesubarrayaresmallerthanthepivotTheelementsinanotherarelargerthanthepivotReturnstheindexofthe“pivot”elementseparatingthetwosubarraysHowdoyousupposeweimplementthis?Partition2023/2/57PartitionInWordsGivenanarrayA[0,…,n-1],wecanpartitionthearraylikethese:(1)Initial:selectanelementtoactasthe“pivot”(which?),letiandjindicatetheindexofsecondleftandrightelementswhichwillbeusedtocomparewiththepivot.(2)Scanfromleft:IncreaseiuntilA[i]greaterthanandequaltothepivot.(3)Scanfromright:DecreasejuntilA[j]smallerthanandequaltothepivot.(4)SwapA[i]andA[j](5)Repeat(2),(3)and(4)untilj≤i.(6)SwapA[i]andA[j],swapA[0]andA[j],returnj.2023/2/58PartitionexampleInitiallist{6,7,5,2,5,8}{6,7,5,2,5,8}{6,5,5,2,7,8}{6,5,5,2,7,8}Done!Quciksortisnotstable{6,7,5,2,5,8}{2,5,5}6{7,8}2023/2/59PartitionAlgorithm(I)ALGORITHMPartition1(A,l,r)

//Input:AsubarrayA[l…r]ofA[0…n-1],definedbyitsleft//andrightindiceslandr(l<r)//Output:ApartitionofA[l…r],withthesplitposition//returnedasthisfunction’svalue

p←A[l]

i←l;j←r+1

repeat

repeat

i←i+1untilA[i]≥p

repeat

j←j-1untilA[j]≤pswap(A[i],A[j]);

until

i≥j

swap(A[i],A[j])//undolastsi≥j

swap(A[l],A[j]

return

j

//jisthefinalindexofpivot

AnyProblem?2023/2/510PartitionAlgorithm(II)ALGORITHMPartition1(A,l,r)

//Input:AsubarrayA[l…r]ofA[0…n-1],definedbyitsleft//andrightindiceslandr(l<r)//Output:ApartitionofA[l…r],withthesplitposition//returnedasthisfunction’svalue

p←A[l];j←l

fori

←l+1tordo

ifA[i]≤

p

j←j+1

if

j≠iswap(A[j],A[i])

end

if

end

for swap(A[l],A[j])

return

j

//jisthefinalindexofpivot

Whynot“<“?2023/2/511QuicksortExample2023/2/512AnalyzingQuicksortWhatwillbethebestcaseforthealgorithm?Partitionisperfectlybalanced,thismeansthatthearrayisdividedintotwoequallengthsubarrays.Inthebestcase:Tbest(1)=0Tbest(n)=2Tbest(n/2)+n-1Whatdoestherecurrencerelationworkoutto?T(n)=(nlogn)2023/2/513AnalyzingQuicksortWhatwillbetheworstcaseforthealgorithm?PartitionisalwaysunbalancedWillanyparticularinputelicittheworstcase?Yes:Already-sortedinputIntheworstcase,Partitionwilldon-1comparisons,butcreateonepartitionthathasn-1elementsandtheotherwillhavenoelementsBecausewewindupjustreducingthepartitionbyoneelementeachtime,worstcaseisgivenby:T(1)=0T(n)=T(n-1)+n-1TherecurrencerelationworksouttoT(n)=(n2)2023/2/514ImprovingQuicksortTherealliabilityofquicksortisthatitrunsinO(n2)onalready-sortedinputDiscussestwosolutions:Randomizetheinputarray,ORPickarandompivotelementHowwillthesesolvetheproblem?ByinsuringthatnoparticularinputcanbechosentomakequicksortruninO(n2)time2023/2/515AnalyzingQuicksort:AverageCaseAssumingrandominput,average-caserunningtimeismuchclosertoΘ(nlogn)thanO(n2)First,amoreintuitiveexplanation/example:Supposethatpartitionalwaysproducesa9-to-1split.Thislooksquiteunbalanced!Therecurrenceisthus: T(n)=T(9n/10)+T(n/10)+n-1

Howdeepwilltherecursiongo?(drawit)2023/2/516AnalyzingQuicksort:AverageCaseIntuitively,areal-liferunofquicksortwillproduceamixof“bad”and“good”splitsRandomlydistributedamongtherecursiontreePretendforintuitionthattheyalternatebetweenbest-case(n/2:n/2)andworst-case(n-1:0)Whathappensifwebad-splitrootnode,thengood-splittheresultingsize(n-1)node?2023/2/517AnalyzingQuicksort:AverageCaseIntuitively,areal-liferunofquicksortwillproduceamixof“bad”and“good”splitsRandomlydistributedamongtherecursiontreePretendforintuitionthattheyalternatebetweenbest-case(n/2:n/2)andworst-case(n-1:0)Whathappensifwebad-splitrootnode,thengood-splittheresultingsize(n-1)node?Weendupwiththreesubarrays,size0,(n-1)/2,(n-1)/2Combinedcostofsplits=n-1+n-2=2n-3=O(n)Noworsethanifwehadgood-splittherootnode!2023/2/518AnalyzingQuicksort:AverageCaseIntuitively,theO(n)costofabadsplit

(or2or3badsplits)canbeabsorbed

intotheO(n)costofeachgoodsplitThusrunningtimeofalternatingbadandgoodsplitsisstillO(nlogn),withslightlyhigherconstantsHowcanwebemorerigorous?2023/2/519AnalyzingQuicksort:AverageCaseForsimplicity,assume:Allinputsdistinct(norepeats)Slightlydifferentpartitionprocedurepartitionaroundarandomelement,whichisnotincludedinsubarraysallsplits(0:n-1,1:n-2,2:n-3,…,n-1:0)equallylikelyWhatistheprobabilityofaparticularsplithappening?Answer:1/n2023/2/520AnalyzingQuicksort:AverageCaseSopartitiongeneratessplits

(0:n-1,1:n-2,2:n-3,…,n-2:1,n-1:0)

eachwithprobability1/nIfT(n)istheexpectedrunningtime,Whatiseachtermunderthesummationfor?Whatisthe(n)termfor?

2023/2/521AnalyzingQuicksort:AverageCaseSo…2023/2/522AnalyzingQuicksort:AverageCaseWecansolvethisrecurrenceusingthedreadedsubstitutionmethodGuesstheanswerAssumethattheinductivehypothesisholdsSubstituteitinforsomevalue<nProvethatitfollowsforn2023/2/523AnalyzingQuicksort:AverageCaseWecansolvethisrecurrenceusingthedreadedsubstitutionmethodGuesstheanswerWhat’stheanswer?AssumethattheinductivehypothesisholdsSubstituteitinforsomevalue<nProvethatitfollowsforn2023/2/524AnalyzingQuicksort:AverageCaseWecansolvethisrecurrenceusingthedreadedsubstitutionmethodGuesstheanswerT(n)=Θ(nlogn)AssumethattheinductivehypothesisholdsSubstituteitinforsomevalue<nProvethatitfollowsforn2023/2/525AnalyzingQuicksort:AverageCaseWecansolvethisrecurrenceusingthedreadedsubstitutionmethodGuesstheanswerT(n)=Θ(nlogn)AssumethattheinductivehypothesisholdsWhat’stheinductivehypothesis?Substituteitinforsomevalue<nProvethatitfollowsforn2023/2/526AnalyzingQuicksort:AverageCaseWecansolvethisrecurrenceusingthedreadedsubstitutionmethodGuesstheanswerT(n)=Θ(nlogn)AssumethattheinductivehypothesisholdsT(n)anlogn+bforsomeconstantsaandbSubstituteitinforsomevalue<nProvethatitfollowsforn2023/2/527AnalyzingQuicksort:AverageCaseWecansolvethisrecurrenceusingthedreadedsubstitutionmethodGuesstheanswerT(n)=Θ(nlogn)AssumethattheinductivehypothesisholdsT(n)anlogn+bforsomeconstantsaandbSubstituteitinforsomevalue<nWhatvalue?Provethatitfollowsforn2023/2/528AnalyzingQuicksort:AverageCaseWecansolvethisrecurrenceusingthedreadedsubstitutionmethodGuesstheanswerT(n)=Θ(nlogn)AssumethattheinductivehypothesisholdsT(n)anlogn+bforsomeconstantsaandbSubstituteitinforsomevalue<nThevaluekintherecurrenceProvethatitfollowsforn2023/2/529Whatarewedoinghere?AnalyzingQuicksort:AverageCaseTherecurrencetobesolvedWhatarewedoinghere?Whatarewedoinghere?PlugininductivehypothesisExpandoutthek=0case2b/nisjustaconstant,

sofolditinto(n)2023/2/530Whatarewedoinghere?Whatarewedoinghere?Evaluatethesummation:

b+b+…+b=b(n-1)TherecurrencetobesolvedSincen-1<n,2b(n-1)/n<2bAnalyzingQuicksort:AverageCaseWhatarewedoinghere?DistributethesummationThissummationgetsitsownsetofslideslater2023/2/531Howdidwedothis?Pickalargeenoughthat

an/4dominates(n)+b

Whatarewedoinghere?Remember,ourgoalistogetT(n)anlogn+bWhatthehell?We’llprovethislaterWhatarewedoinghere?Distributethe(2a/n)termTherecurrencetobesolvedAnalyzingQuicksort:AverageCase2023/2/532AnalyzingQuicksort:AverageCaseSoT(n)anlogn+bforcertainaandbThustheinductionholdsThusT(n)=Θ(nlogn)ThusquicksortrunsinΘ(nlogn)timeonaverage(phew!)Ohyeah,thesummation…2023/2/533Whatarewedoinghere?ThelogkinthesecondtermisboundedbylognTightlyBoundingoftheKeySummationWhatarewedoinghere?MovethelognoutsidethesummationWhatarewedoinghere?Splitthesummationforatighterbound2023/2/534ThesummationboundsofarTightlyBoundingoftheKeyS