基本计算机算法排序课件

基本计算机算法：排序QuickQuiz1.Inthesequentialsearchalgorithm,theminimumamountofworkisdoneifNAMEisthe____nameinthelist.2.The____caseofanalgorithmrequirestheminimumamountofwork.3.The____caseofanalgorithmrequiresthemaximumamountofwork.4.Theselectionsortalgorithmdoesthesameamountofworknomatterhowthenumbersareinitiallyarranged.TrueorFalse?5.ngrowsatamuchfasterratethann2.TrueorFalse?Answer:firstAnswer:bestAnswer:worstAnswer:TrueAnswer:falseQUICKSORTGetalistofnelementstosort.Partitionthelistwiththesmallestelementsinthefirstpartandthelargestelementsinthesecondpart.SortthefirstpartusingQuicksort.SortthesecondpartusingQuicksort.Stop.Highleveldescriptionofquicksort:TwoProblemstoDealWith:1)Whatisthepartitioningandhowdoweaccomplishit?2)Howdowesortthetwoparts?Let’sdealwith(2)first:Tosortasublist,wewillusethesamestrategyasontheentirelist-i.e.Partitionthelistwiththesmallestelementsinthefirstpartandthelargestelementsinthesecondpart.SortthefirstpartusingQuicksort.SortthesecondpartusingQuicksort.Obviouslywhenalistorsublisthaslength1,itissorted.TheFirstQuicksortProblemQuestion(1):Whatisthepartitioningandhowdoweaccomplishit?AnelementfromthelistcalledpivotisusedtodividelistintotwosublistsWefollowcommonpracticeofusingthefirstelementoflistasthepivot.WeusethepivottocreateAleftsublistcontainsthoseelements≤thepivotArightsublistcontainsthoseelements>thepivot.PartitioningExampleTheleftpointermovesrightuntilavalue>3isfoundNext,rightpointermovesleftuntilavalue≤3isfoundThesetwovaluesareswapped,andprocessrepeats

3

45168730

3

45168730

3

05168734

3

05168734

3

03168754

3

03168754PartitioningExample(cont)

3

03168754

1

03

3

68754

≤pivot

pivot

>pivotPartitioningstopswhentheleft(white)pointer≥theright(blue)pointer.Atthispoint,thelistitemsatthepivotandrightpointerareswapped.PartitioningAlgorithm1.Setthepivottothefirstelementinlist2.SettheleftmarkerLtothefirstelementofthelist3.SettherightmarkerRtothelastelement(nth)ofthelist4.WhileLislessthanR,doSteps5-95.WhileelementatLisnotlargerthanpivotandL≤n6.MoveLtotherightoneposition7.WhileelementatRislargerthanpivotandR≥18.MoveRtotheleftoneposition9.IfLisleftofRthenexchangeelementsatLandR.10.ExchangethepivotwithelementatR.11.StopQuicksortComplexityBestcasetimecomplexity(nlgn)Averagecasetimecomplexity(nlgn)Worstcaserunningtime(n2)Worstcaseexamples???AlistthatisalreadysortedAlistthatisreversesorted(largesttosmallest)Figure3.22Order-of-MagnitudeTimeEfficiencySummaryQuickQuizIntheshuffle-leftalgorithm,thebestcaseoccurswhenthelisthasno0values.TrueorFalse?2.Thebestcasefortheconverging-pointersalgorithmisalistofall0entries.TrueorFalse?3.Thebinarysearchalgorithmworksonlyonalistthathasalreadybeen____.Answer:TrueAnswer:FalseAnswer:sortedFigure3.25Comparisonsoflgn,n,n2,and2nFigure3.27AComparisonofFourOrdersofMagnitudeWhenThingsGetOutOfHand:HamiltonianCircuitsApaththatbeginsandendsatthesamenodeandgoesthroughallothernodesexactlyoncefollowingtheedges.ABCDSatisfiabilityProblem(AorB)and(¬Bor¬C)(AorB)and(BorC)and(¬Aor¬B)(AorB)and(¬Bor¬C)and(¬A)(AorB)and(¬Aor¬C)and(¬BorC)and(AorBor¬C)BinPackingProblemGiven:anunlimitednumberofbinsofvolume1unitNobjectsofvolumebetween0.0and1.0Find:TheminimumnumberofbinstostorethenobjectsApproximationAlgorithmsHowwouldyougoaboutsolvingthebin-packingproblemquicklyevenifitisthebestsolution?(Everseehowluggageispackedonanairplane?)AnAlgorithmisAwell-orderedcollectionofUnambiguousandEffectivelycomputableoperationsthat,whenexecutedProducesaresultandHaltsinafiniteamountoftimeTextbookdefinitionPropertiesofAlgorithmsCorrectnessDoesthealgorithmalwaysworkClarityIsthealgorithmeasytounderstandElegance(Style)Example:Gaussaskedtoaddnumbersfrom1to100EfficiencySpeedofalgorithmSpacerequiredtorunalgorithmEfficiencyofAlgorithmsHowlongdoesittakeanalgorithmtorun?DependsoncomputerDependsoninputdataBenchmarkingRunsamealgorithmandsameinputondifferencemachinesRunssamealgorithmonsamemachineusingdifferenceinputNeedamethodofmeasuringinherentefficiencyofalgorithm,independentofmachineorinputCounthowmanytimes“workunit”isexecutedGameTimeGuessMyNumber20QuestionsGuessWho?ForEachofthesegamesunderstanddifferentstrategiesforfindingtheanswer.Whatisthebeststrategy?TelephoneBookExampleTaskFindaparticularperson’snumberfromalistoftelephonesubscribers,giventhenameSequentialSearchAlgorithmoutlineStartwiththefirstentryandcheckitsname,thenrepeattheprocessforallentriesFigure3.1SequentialSearchAlgorithmHowEfficientistheAlgorithm?BestCase:WorstCase:AverageCase:1ComparisonNComparisonsN/2ComparisonsOrderofMagnitudeTotalnumberofoperationsperformedissomeconstantnumberofoperationstimesN2N3N½*NLinear

(n)Figure3.4Work=cnforVariousValuesofcTelephoneBookExample2TaskFindaparticularperson’snumberfromasortedlistoftelephonesubscribers,giventhenameBinarySearchAlgorithmoutlineAlwaysselectthemiddlename.Ifthepersonsnameisgreaterthanselectednamethensearchtophalf,otherwisesearchbottomhalfofremainingnames.Figure3.18BinarySearchAlgorithm(listmustbesorted)HowEfficientistheAlgorithm?BestWorstAverage1ComparisonLogNComparisons(Logn)

AboutLogNComparisons(Logn)Figure3.21AComparisonofnandlgnDataCleanupAlgorithmsGivenacollectionofnumbers,findandremoveallzerosPossiblealgorithmsShuffle-leftCopy-overConverging-pointersTheShuffle-LeftAlgorithmScanlistfromlefttorightWhenazeroisfound,shiftallvaluestoitsrightoneslottotheleftFigure3.14TheShuffle-LeftAlgorithmforDataCleanupTheShuffle-LeftAlgorithm(continued)TimeefficiencyCountexaminationsoflistvaluesandshiftsBestcaseNoshifts,nexaminations

(n)WorstcaseShiftateachpass,npassesn2shiftsplusnexaminations

(n2)TheShuffle-LeftAlgorithm(continued)Spaceefficiencynslotsfornvalues,plusafewlocalvariables

(n)TheCopy-OverAlgorithmUseasecondlistCopyovereachnonzeroelementinturnFigure3.15TheCopy-OverAlgorithmforDataCleanupTheCopy-OverAlgorithmTimeefficiencyCountexaminationsandcopiesBestcaseAllzerosnexaminationsand0copies

(n)TheCopy-OverAlgorithm(continued)Timeefficiency(continued)WorstcaseNozerosnexaminationsandncopies

(n)Spaceefficiency2nslotsfor