第04章排序集合和選擇SortingSetsandSelection課件

MergeSort7294

247972

2794

497

72

29

94

41Chapter4OutlineandReadingDivide-and-conquerparadigm,MergeSort(§4.1)Sets(§4.2);GenericMergingandsetoperations(§4.2.1)Note:Sections4.2.2and4.2.3areOptionalQuick-sort(§4.3)Analysisofquick-sort((§4.3.1)ALowerBoundonComparison-basedSorting(§4.4)QuickSortandRadixSort(§4.5)In-placequick-sort(§4.8)ComparisonofSortingAlgorithm(§4.6)Selection(§4.7)2Chapter4Divide-and-ConquerDivide-andconquerisageneralalgorithmdesignparadigm:Divide:dividetheinputdataSintwodisjointsubsetsS1

andS2Recur:solvethesubproblemsassociatedwithS1

andS2Conquer:combinethesolutionsforS1

andS2intoasolutionforSThebasecasefortherecursionaresubproblemsofsize0or1Merge-sortisasortingalgorithmbasedonthedivide-and-conquerparadigmLikeheap-sortItusesacomparatorIthasO(nlogn)runningtimeUnlikeheap-sortItdoesnotuseanauxiliarypriorityqueueItaccessesdatainasequentialmanner(suitabletosortdataonadisk)3Chapter4Merge-SortMerge-sortonaninputsequenceSwithnelementsconsistsofthreesteps:Divide:partitionSintotwosequencesS1

andS2ofaboutn/2elementseachRecur:recursivelysortS1

andS2Conquer:mergeS1

andS2intoauniquesortedsequenceAlgorithm

mergeSort(S,C)

Input

sequenceSwithn elements,comparatorC

Output

sequenceSsorted accordingtoCif

S.size()>1

(S1,S2)

partition(S,n/2)

mergeSort(S1,C)

mergeSort(S2,C)

S

merge(S1,S2)4Chapter4MergingTwoSortedSequencesTheconquerstepofmerge-sortconsistsofmergingtwosortedsequencesAandBintoasortedsequenceScontainingtheunionoftheelementsofAandBMergingtwosortedsequences,eachwithn/2elementsandimplementedbymeansofadoublylinkedlist,takesO(n)timeAlgorithm

merge(A,B)

Input

sequencesAandBwith

n/2elementseach

Output

sortedsequenceofABS

emptysequencewhile

A.isEmpty()

B.isEmpty()

if

A.first().element()

<

B.first().element()

S.insertLast(A.remove(A.first()))

else

S.insertLast(B.remove(B.first()))while

A.isEmpty() S.insertLast(A.remove(A.first()))while

B.isEmpty() S.insertLast(B.remove(B.first()))returnS5Chapter4Merge-SortTreeAnexecutionofmerge-sortisdepictedbyabinarytreeeachnoderepresentsarecursivecallofmerge-sortandstoresunsortedsequencebeforetheexecutionanditspartitionsortedsequenceattheendoftheexecutiontherootistheinitialcalltheleavesarecallsonsubsequencesofsize0or17294

247972

2794

497

72

29

94

46Chapter4ExecutionExamplePartition72942479386113867227944938386116772299443388661172943861

123467897Chapter4ExecutionExample(cont.)Recursivecall,partition7294

2479386113867227944938386116772299443388661172943861

123467898Chapter4ExecutionExample(cont.)Recursivecall,partition7294

24793861138672

27944938386116772299443388661172943861

123467899Chapter4ExecutionExample(cont.)Recursivecall,basecase7294

24793861138672

279449383861167

72299443388661172943861

1234678910Chapter4ExecutionExample(cont.)Recursivecall,basecase7294

24793861138672

279449383861167

72

299443388661172943861

1234678911Chapter4ExecutionExample(cont.)Merge7294

24793861138672

279449383861167

72

299443388661172943861

1234678912Chapter4ExecutionExample(cont.)Recursivecall,…,basecase,merge7294

24793861138672

2794

49383861167

72

23388661172943861

123467899

94

413Chapter4ExecutionExample(cont.)Merge7294

24793861138672

2794

49383861167

72

29

94

43388661172943861

1234678914Chapter4ExecutionExample(cont.)Recursivecall,…,merge,merge7294

24793861

136872

2794

4938

3861

167

72

29

94

43

38

86

61

172943861

1234678915Chapter4ExecutionExample(cont.)Merge7294

24793861

136872

2794

4938

3861

167

72

29

94

43

38

86

61

172943861

1234678916Chapter4AnalysisofMerge-SortTheheighthofthemerge-sorttreeisO(logn)

ateachrecursivecallwedivideinhalfthesequence,TheoverallamountorworkdoneatthenodesofdepthiisO(n)

wepartitionandmerge2isequencesofsizen/2i

wemake2i+1recursivecallsThus,thetotalrunningtimeofmerge-sortisO(nlogn)depth#seqssize01n12n/2i2in/2i………17Chapter4Sets18Chapter4SetOperationsWerepresentasetbythesortedsequenceofitselementsByspecializingtheauxliliarymethodshegenericmergealgorithmcanbeusedtoperformbasicsetoperations:unionintersectionsubtractionTherunningtimeofanoperationonsetsAandBshouldbeatmostO(nA

+

nB)Setunion:aIsLess(a,S)

S.insertFirst(a)bIsLess(b,S)

S.insertLast(b)bothAreEqual(a,b,S)

S.insertLast(a)Setintersection:aIsLess(a,S)

{donothing}bIsLess(b,S)

{donothing}bothAreEqual(a,b,S)

S.insertLast(a)19Chapter4StoringaSetinaListWecanimplementasetwithalistElementsarestoredsortedaccordingtosomecanonicalorderingThespaceusedisO(n)ListNodesstoringsetelementsinorderSetelements20Chapter4GenericMergingGeneralizedmergeoftwosortedlistsAandBTemplatemethodgenericMergeAuxiliarymethodsaIsLessbIsLessbothAreEqualRunsinO(nA

+

nB)timeprovidedtheauxiliarymethodsruninO(1)timeAlgorithm

genericMerge(A,B)

S

emptysequencewhile

A.isEmpty()

B.isEmpty()

a

A.first().element();b

B.first().element()

if

a

<

b

aIsLess(a,S);A.remove(A.first())

elseifb

<

a

bIsLess(b,S);B.remove(B.first())

else{b=a}

bothAreEqual(a,b,S)

A.remove(A.first());B.remove(B.first())while

A.isEmpty()

aIsLess(a,S);A.remove(A.first())while

B.isEmpty() bIsLess(b,S);B.remove(B.first())returnS21Chapter4UsingGenericMergeforSetOperationsAnyofthesetoperationscanbeimplementedusingagenericmergeForexample:Forintersection:onlycopyelementsthatareduplicatedinbothlistForunion:copyeveryelementfrombothlistsexceptfortheduplicatesAllmethodsruninlineartime.22Chapter4Quick-Sort74962

2467942

2479

792

29

923Chapter4Quick-SortQuick-sortisarandomizedsortingalgorithmbasedonthedivide-and-conquerparadigm:Divide:pickarandomelementx(calledpivot)andpartitionSintoLelementslessthanxEelementsequalxGelementsgreaterthanxRecur:sortLandGConquer:joinL,E

andGxxLGEx24Chapter4PartitionWepartitionaninputsequenceasfollows:Weremove,inturn,eachelementyfromSandWeinsertyintoL,E

orG,

dependingontheresultofthecomparisonwiththepivotxEachinsertionandremovalisatthebeginningorattheendofasequence,andhencetakesO(1)timeThus,thepartitionstepofquick-sorttakesO(n)timeAlgorithm

partition(S,

p)

Input

sequenceS,positionpofpivot

Output

subsequencesL,

E,Gofthe

elementsofSlessthan,equalto,

orgreaterthanthepivot,resp.

L,

E,G

emptysequencesx

S.remove(p)

while

S.isEmpty()

y

S.remove(S.first())

if

y

<

x

L.insertLast(y)

elseify

=

x

E.insertLast(y)

else

{y>x}

G.insertLast(y)returnL,

E,G25Chapter4Quick-SortTreeAnexecutionofquick-sortisdepictedbyabinarytreeEachnoderepresentsarecursivecallofquick-sortandstoresUnsortedsequencebeforetheexecutionanditspivotSortedsequenceattheendoftheexecutionTherootistheinitialcallTheleavesarecallsonsubsequencesofsize0or174962

2467942

2479

792

29

926Chapter4ExecutionExamplePivotselection729424792272943761

123467893861138633889449994427Chapter4ExecutionExample(cont.)Partition,recursivecall,pivotselection

2431

24799449994472943761

123467893861138633882228Chapter4ExecutionExample(cont.)Partition,recursivecall,basecase

2431

2471

19449994472943761

1234678938611386338829Chapter4ExecutionExample(cont.)Recursivecall,pivotselection797113868872943761

123467892431

12

341

143

3

4994

49930Chapter4ExecutionExample(cont.)Partition,…,recursivecall,basecase797113868872943761

123467892431

12

341

143

3

4994

49

931Chapter4ExecutionExample(cont.)Join,join797

17

7

98872943761

12346

7792431

12

341

143

3

4994

49

932Chapter4Worst-caseRunningTimeTheworstcaseforquick-sortoccurswhenthepivotistheuniqueminimumormaximumelementOneofLandGhassizen-1andtheotherhassize0Therunningtimeisproportionaltothesumn

+(n

-1)+…+2+1Thus,theworst-caserunningtimeofquick-sortisO(n2)depthtime0n1n

-1……n

-11…33Chapter4ExpectedRunningTimeConsiderarecursivecallofquick-sortonasequenceofsizesGoodcall:thesizesofLandGareeachlessthan3s/4Badcall:oneofLandGhassizegreaterthan3s/4Acallisgoodwithprobability1/21/2ofthepossiblepivotscausegoodcalls:7971172943761924317294376172943761GoodcallBadcall12345678910111213141516GoodpivotsBadpivotsBadpivots34Chapter4ExpectedRunningTime,Part2ProbabilisticFact:Theexpectednumberofcointossesrequiredinordertogetkheadsis2kForanodeofdepthi,weexpecti/2ancestorsaregoodcallsThesizeoftheinputsequenceforthecurrentcallisatmost(3/4)i/2nTherefore,wehaveForanodeofdepth2log4/3n,theexpectedinputsizeisoneTheexpectedheightofthequick-sorttreeisO(logn)TheamountorworkdoneatthenodesofthesamedepthisO(n)Thus,theexpectedrunningtimeofquick-sortisO(nlogn)35Chapter4In-PlaceQuick-SortQuick-sortcanbeimplementedtorunin-placeInthepartitionstep,weusereplaceoperationstorearrangetheelementsoftheinputsequencesuchthattheelementslessthanthepivothaveranklessthanhtheelementsequaltothepivothaverankbetweenhandktheelementsgreaterthanthepivothaverankgreaterthankTherecursivecallsconsiderelementswithranklessthanhelementswithrankgreaterthankAlgorithm

inPlaceQuickSort(S,

l,

r)

Input

sequenceS,rankslandr

OutputsequenceSwiththe

elementsofrankbetweenlandr

rearrangedinincreasingorder

if

lr

returni

arandomintegerbetweenlandr

x

S.elemAtRank(i)

(h,

k)

inPlacePartition(x)inPlaceQuickSort(S,

l,

h-1)inPlaceQuickSort(S,

k+1,

r)36Chapter4In-PlacePartitioningPerformthepartitionusingtwoindicestosplitSintoLandEUG(asimilarmethodcansplitEUGintoEandG).Repeatuntiljandkcross:Scanjtotherightuntilfindinganelement>x.Scanktotheleftuntilfindinganelement<x.Swapelementsatindicesjandk32510735927989769jk(pivot=6)32510735927989769jk37Chapter4ExecutionExample(cont.)Recursivecall,…,basecase,join38611386338872943761

123467892431

12

341

143

3

4994

438Chapter4ALowerBoundonComparison-basedSorting(§4.4)39Chapter4Comparison-BasedSortingManysortingalgorithmsarecomparisonbased.TheysortbymakingcomparisonsbetweenpairsofobjectsExamples:bubble-sort,selection-sort,insertion-sort,heap-sort,merge-sort,quick-sort,...Letusthereforederivealowerboundontherunningtimeofanyalgorithmthatusescomparisonstosortnelements,x1,x2,…,xn.Isxi<xj?yesno40Chapter4CountingComparisonsLetusjustcountcomparisonsthen.Eachpossiblerunofthealgorithmcorrespondstoaroot-to-leafpathinadecisiontree41Chapter4DecisionTreeHeightTheheightofthisdecisiontreeisalowerboundontherunningtimeEverypossibleinputpermutationmustleadtoaseparateleafoutput.Ifnot,someinput…4…5…wouldhavesameoutputorderingas…5…4…,whichwouldbewrong.Sincetherearen!=1*2*…*nleaves,theheightisatleastlog(n!)42Chapter4TheLowerBoundAnycomparison-basedsortingalgorithmstakesatleastlog(n!)timeTherefore,anysuchalgorithmtakestimeatleastThatis,anycomparison-basedsortingalgorithmmustruninΩ(nlogn)time.43Chapter4Bucket-SortandRadix-Sort0123456789B1,c7,d7,g3,b3,a7,e44Chapter4Bucket-Sort(§4.5.1)LetbeSbeasequenceofn(key,element)itemswithkeysintherange[0,N

-1]Bucket-sortusesthekeysasindicesintoanauxiliaryarrayBofsequences(buckets)Phase1:EmptysequenceSbymovingeachitem(k,o)intoitsbucketB[k]Phase2:Fori=0,…,

N-

1,movetheitemsofbucketB[i]totheendofsequenceSAnalysis:Phase1takesO(n)timePhase2takesO(n

+N)time Bucket-sorttakesO(n

+N)timeAlgorithm

bucketSort(S,

N)

Input

sequenceSof(key,element)

itemswithkeysintherange

[0,N

-1]

Output

sequenceSsortedby

increasingkeys

B

arrayofNemptysequenceswhile

S.isEmpty() f

S.first() (k,o)

S.remove(f)

B[k].insertLast((k,o))fori

0to

N-

1

while

B[i].isEmpty()

f

B[i].first() (k,o)

B[i].remove(f)

S.insertLast((k,o))45Chapter4ExampleKeyrange[0,9]7,d1,c3,a7,g3,b7,e1,c3,a3,b7,d7,g7,ePhase1Phase20123456789B1,c7,d7,g3,b3,a7,e46Chapter4PropertiesandExtensionsKey-typePropertyThekeysareusedasindicesintoanarrayandcannotbearbitraryobjectsNoexternalcomparatorStableSortPropertyTherelativeorderofanytwoitemswiththesamekeyispreservedaftertheexecutionofthealgorithmExtensionsIntegerkeysintherange[a,b]Putitem(k,o)intobucket

B[k-a]

StringkeysfromasetDofpossiblestrings,whereDhasconstantsize(e.g.,namesofthe50U.S.states)SortDandcomputetherankr(k)

ofeachstringkofDinthesortedsequencePutitem(k,o)intobucket

B[r(k)]47Chapter4LexicographicOrderAd-tupleisasequenceofdkeys(k1,k2,…,kd),wherekeykiissaidtobethei-thdimensionofthetupleExample:TheCartesiancoordinatesofapointinspacearea3-tupleThelexicographicorderoftwod-tuplesisrecursivelydefinedasfollows(x1,x2,…,xd)<(y1,y2,…,yd)

x1<

y1

x1

=

y1

(x2,…,xd)<(y2,…,yd)

I.e.,thetuplesarecomparedbythefirstdimension,thenbytheseconddimension,etc.48Chapter4Lexicographic-SortLetCibethecomparatorthatcomparestwotuplesbytheiri-thdimensionLetstableSort(S,C)beastablesortingalgorithmthatusescomparatorCLexicographic-sortsortsasequenceofd-tuplesinlexicographicorderbyexecutingdtimesalgorithmstableSort,oneperdimensionLexicographic-sortrunsinO(dT(n))time,whereT(n)istherunningtimeofstableSortAlgorithm

lexicographicSort(S)

Input

sequenceSofd-tuples

Output

sequenceSsortedin

lexicographicorder

fori

d

downto1 stableSort(S,Ci)Example:(7,4,6)(5,1,5)(2,4,6)(2,1,4)(3,2,4)(2,1,4)(3,2,4)(5,1,5)(7,4,6)(2,4,6)(2,1,4)(5,1,5)(3,2,4)(7,4,6)(2,4,6)(2,1,4)(2,4,6)(3,2,4)(5,1,5)(7,4,6)49Chapter4Radix-Sort(§4.5.2)Radix-sortisaspecializationoflexicographic-sortthatusesbucket-sortasthestablesortingalgorithmineachdimensionRadix-sortisapplicabletotupleswherethekeysineachdimensioniareintegersintherange[0,N

-1]Radix-sortrunsintimeO(d(n

+N))Algorithm

radixSort(S,N)

Input

sequenceSofd-tuplessuch that(0,…,0)(x1,…,xd)and

(x1,…,xd)(N

-1,…,N

-1)

foreachtuple(x1,…,xd)inS

Output

sequenceSsortedin

lexicographicorder

fori

d

downto1 bucketSort(S,N)50Chapter4Radix-SortforBinaryNumbersConsiderasequenceofn

b-bitintegers

x

=

xb

-1…x1x0Werepresenteachelementasab-tupleofintegersintherange[0,1]andapplyradix-sortwithN

=2Thisapplicationoftheradix-sortalgorithmrunsinO(bn)timeForexample,wecansortasequenceof32-bitintegersinlineartimeAlgorithm

binaryRadixSort(S)

Input

sequenceSofb-bit

integers

Output

sequenceSsorted replaceeachelementx

ofSwiththeitem(0,x)

fori

0to

b-1 replacethekeykof

eachitem(k,x)ofS withbitxiofx

bucketSort(S,2)51Chapter4ExampleSortingasequenceof4-bitintegers100100101101000111100010111010011101000110011101000100101110100100010010110111100001001010011101111052Chapter4SummaryofSortingAlgorithms(§4.6)AlgorithmTimeNotesselection-sortO(n2)slowin-placeforsmalldatasets(<1K)insertion-sortO(n2)slowin-placeforsmalldatasets(<1K)heap-sortO(nlogn)fastin-placeforlargedatasets(1K—1M)merge-sortO(nlogn)fastsequentialdataaccessforhugedatasets(>1M)53Chapter4Selection(§4.7)54Chapter4TheSelectionProblemGivenanintegerkandnelementsx1,x2,…,xn,takenfromatotalorder,findthek-thsmallestelementinthisset.Ofcourse,wecansortthesetinO(nlogn)timeandthenindexthek-thelement.Canwesolvetheselectionproblemfaster?74962

24679k=355Chapter4Quick-SelectQuick-selectisarandomizedselectionalgorithmbasedontheprune-and-searchparadigm:Prune:pickarandomelementx(calledpivot)andpartitionSintoLelementslessthanxEelementsequalxGelementsgreaterthanxSearch:dependingonk,eitheranswerisinE,orweneedtorecurseineitherLorGxxLGEk<|L||L|<k<|L|+|E|(done)k>|L|+|E|k’=k-|L|-|E|56Chapter4PartitionWepartitionaninputsequenceasinthequick-sortalgorithm:Weremove,inturn,eachelementyfromSandWeinsertyintoL,E

orG,

dependingontheresultofthecomparisonwiththepivotxEachinsertionandremovalisatthebeginningorattheendofasequence,andhence