T&RTeamofAlgorithmDesignCollegeofComputerScienceandEngineering,CQUAlgorithmAnalysis&Design

IntroductiontoAlgorithmChapter7:QuickSortOutline6.1BasicQuickSort6.2ImprovingQuickSortwithMedians7.1BasicQuickSortQUICKSORTWehaveseentwoO(nlogn)sortingalgorithms:MergesortwhichisfasterbutrequiresmorememoryHeapsortwhichallowsin-placesortingWewillnowlookatarecursivealgorithmwhichmaybedonealmostinplaceandusuallyfasterthanheapsortUseanobjectinthearray(apivot)todividethetwoAveragecase: O(nlogn)timeandO(logn)memoryWorstcase: O(n2)timeandO(n)memoryQUICKSORTMergesortsplitsthearraysub-listsandsortsthemThelargerproblemissplitintotwosub-problemsbasedonlocationinthearrayConsiderthefollowingalternative:ChoseanobjectinthearrayandpartitiontheremainingobjectsintotwogroupsrelativetothechosenentryQUICKSORTForexample,givenanunsortedarray:Wecanselectthelastentry,4,andsorttheremainingentriesintotwogroups,thoselessthan4andthosegreaterthan4:Notethat4

isnowinthecorrectlocationoncethelistissortedProceedbyapplyingthealgorithmtothefirst3andlast4entries2871356421347568ASimpleImplementation–PARTITIONPARTITION(A,

p,

r) x←A[r] i←p-1

FOR

j←pTO

r-1

IF

A[j]≤x

THENi←i+1 exchangeA[i]?A[j] exchangeA[i+1]?A[r]

RETURN

i+1ASimpleImplementation–PARTITIONA[p,…,i]:knowntobe≤pivotA[i+1,…,j-1]:knowntobe>pivotA[j…r-1]:notyetexaminedA[r]:pivotASimpleImplementation–PARTITIONTheoperationofPartitiononthesamplearray.Lightlyshadedarrayelementsareallwithvaluesnogreaterthanx(thepivot).Heavilyshadedarrayelementsareallwithvaluesgreaterthanx.ASimpleImplementation–QUICKSORTQUICKSORT(A,p,r)

IFp<r

THENq←PARTITION(A,p,r)

QUICKSORT(A,p,q–1)

QUICKSORT(A,q+1,r)Initialcall:QUICKSORT(A,1,n)Run-timeAnalysisInthebestcase,thelistwillbesplitintotwoapproximatelyequalsub-lists,andthus,theruntimecouldbeverysimilartothatofmergesort:Q(nlogn)RecursiveTreeoftheBestCaseArecursiontreeforquicksortinwhichthepartitionalwaysbalancesthetwosidesofthepartitionequally.TheresultingrunningtimeisQ(nlogn)Thequestionis:WHAThappensifwedon’tgetthatlucky?Worst-caseScenarioSupposewechoosethesmallestelementasourpivotandwetryorderingasortedlist:Using2,wepartitiontheoriginallistintoWestillhavetosortalistofsizen–1TheruntimeisT(n)=T(n–1)+Q(n)=Q(n2)Thus,theruntimedropsfromQ(nlogn)toQ(n2)80389584661079226879612438132803895846610792687961243813RecursiveTreeoftheWorstCaseArecursiontreeforquicksortinwhichthepartitionalwaysputsonlyasingleelementononesideofthepartition.TheresultingrunningtimeisQ(n2)RecursiveTreeoftheBalancedCaseWhatifthesplitisalways1:9?T(n)=T(9n/10)+T(n/10)+Q(n)Whatisthesolutiontothisrecurrence?RecursiveTreeoftheBalancedCaseArecursiontreeforquicksortinwhichpartitionalwaysproducesa9-to-1split,yieldingarunningtimeof

Q(nlogn)7.2ImprovingQuickSortwithMediansAlternateStrategyOurgoalistochoosethemedianelementinthelistasourpivot:Unfortunately,it’sDIFFICULTtofindAlternatestrategy:takethemedianofasubsetofentriesForexample,takethemedianofthefirst,middle,andlastentries8038958466107922687961243813ChoosetheMedian-of-ThreeItisdifficulttofindthemediansoconsideranotherstrategy:Choosethemedianofthefirst,middle,andlastentriesinthelistThiswillusuallygiveamuchbetterapproximationoftheactualmedianChoosetheMedian-of-ThreeSortingtheelementsbasedon44resultsintwosub-lists,eachofwhichmustbesorted(again,usingquicksort)Weselectthe26topartitionthefirstsub-list:and81topartitionthesecondsub-list:ChoosetheMedian-of-Three

ImprovedQuickSortExampleFirst,weexaminethefirst,middle,andlastentriesofthefulllistThespanbelowwillindicatewhichlistwearecurrentlysortingImprovedQuickSortExampleWeselect57tobeourpivotWemove24intothefirstlocationImprovedQuickSortExampleStartingatthe2ndand2nd-lastlocations:wesearchforwardtillwefind

70>57wesearchbackwardtillwefind 49<57ImprovedQuickSortExampleWeswap70and49,placingtheminorderwithrespecttoeachotherImprovedQuickSortExampleWesearchforwarduntilwefind

97>57Wesearchbackwarduntilwefind 16<57ImprovedQuickSortExampleWeswap16and97whicharenowinorderwithrespecttoeachotherImprovedQuickSortExampleWesearchforwardtillwefind 63>57Wesearchbackwardtillwefind 55<57ImprovedQuickSortExampleWeswap63and55ImprovedQuickSortExampleWesearchforwardtillwefind 85>57Wesearchbackwardtillwefind 36<57ImprovedQuickSortExampleWeswap85and36,placingtheminorderwithrespecttoeachotherImprovedQuickSortExampleWesearchforwarduntilwefind 68>57Wesearchbackwarduntilwefind 9<57ImprovedQuickSortExampleWeswap68and9ImprovedQuickSortExampleWesearchforwarduntilwefind 76>57Wesearchbackwarduntilwefind 9<57Theindicesareoutoforder,sowestopImprovedQuickSortExampleWemovethelargerindexeditemtothevacancyattheendofthearrayWefilltheemptylocationwiththepivot,57ThepivotisnowinthecorrectlocationImprovedQuickSortExampleWewillnowrecursivelycallquicksortonthefirsthalfofthelistWhenwearefinished,allentries<57willbesortedImprovedQuickSortExampleWeexaminethefirst,middle,andlastelementsofthissublistImprovedQuickSortExampleWechoose24tobeourpivotWemove9intothefirstlocationinthissub-listImprovedQuickSortExampleWesearchforwardtillwefind 49>24Wesearchbackwardtillwefind 21<24ImprovedQuickSortExampleWeswap49and21,placingtheminorderwithrespecttoeachotherWesearchforwardtillwefind 38>24Wesearchbackwardtillwefind 16<24Theindicesarereversed,sowestopImprovedQuickSortExampleImprovedQuickSortExampleWemove38tothevacantlocationandmovethepivot24intothepreviouslocationof3824isnowinthecorrectlocationImprovedQuickSortExampleWewillnowrecursivelycallquicksortontheleftandrighthalvesofthoseentrieswhichare<57ImprovedQuickSortExampleThefirstpartitionhasthreeentries,sowesortitusinginsertionsortImprovedQuickSortExampleThesecondpartitionalsohasonlyfourentries,soagain,weuseinsertionsortImprovedQuickSortExampleFirstweexaminethefirst,middle,andlastentriesofthesub-listImprovedQuickSortExampleWechoose74tobeourpivotWemove76tothevacancyleftby74ImprovedQuickSortExampleWesearchforwardtillwefind 81>74Wesearchbackwardtillwefind 70<74ImprovedQuickSortExampleWeswap70and84placingtheminorderImprovedQuickSortExampleWesearchforwardtillwefind 85>74Wesearchbackwardtillwefind 61<74ImprovedQuickSortExampleWeswap85and61placingtheminorderImprovedQuickSortExampleWesearchforwardtillwefind 79>74Wesearchbackwardtillwefind 63<74Theindicesarereversed,sowestopImprovedQuickSortExampleWemove79tothevacantlocationandmovethepivot74intopreviouslocationof7974

isnowinthecorrectlocationImprovedQuickSortExampleWesorttheleftsub-listfirstIthas4elements,sowesimplyuseinsertionsortHavingsortedthefourelements,wefocusontheremainingsub-listofsevenentriesImprovedQuickSortExampleImprovedQuickSortExampleTosortthenextsub-list,weexaminethefirst,middle,andlastentriesImprovedQuickSortExampleWeselect79asourpivotandmove:76intothelowestposition85intothehighestpositionImprovedQuickSortExampleWesearchforwardtillwefind 85>79Wesearchbackwardtillwefind 77<79ImprovedQuickSortExampleWeswap85and77,placingtheminorderImprovedQuickSortExampleWesearchforwardtillwefind 97>79Wesearchbackwardtillwefind 77<79Theindicesarereversed,sowestopImprovedQuickSortExampleFinally,wemove97to