04_DS and Algorithm_session_05

Ver.1.0Session5DataStructuresandAlgorithmsObjectivesInthissession,youwilllearnto:SortdatabyusingquicksortSortdatabyusingmergesortSearchdatabyusinglinearsearchtechniqueSearchdatabyusingbinarysearchtechniqueVer.1.0Session5DataStructuresandAlgorithmsQuicksortalgorithm:IsoneofthemostefficientsortingalgorithmsIsbasedonthedivideandconquerapproachSuccessivelydividestheproblemintosmallerpartsuntiltheproblemsbecomesosmallthattheycanbedirectlysolvedSortingDatabyUsingQuickSortVer.1.0Session5DataStructuresandAlgorithmsInquicksortalgorithm,you:Selectanelementfromthelistcalledaspivot.Partitionthelistintotwopartssuchthat:Alltheelementstowardstheleftendofthelistaresmallerthanthepivot.Alltheelementstowardstherightendofthelistaregreaterthanthepivot.Storethepivotatitscorrectpositionbetweenthetwopartsofthelist.Yourepeatthisprocessforeachofthetwosublistscreatedafterpartitioning.Thisprocesscontinuesuntiloneelementisleftineachsublist.ImplementingQuickSortAlgorithmVer.1.0Session5DataStructuresandAlgorithmsTounderstandtheimplementationofquicksortalgorithm,consideranunsortedlistofnumbersstoredinanarray.ImplementingQuickSortAlgorithm(Contd.)arr210435546382816898330567Ver.1.0Session5DataStructuresandAlgorithmsLetussortthisunsortedlist.arr210435546382816898330567ImplementingQuickSortAlgorithm(Contd.)Ver.1.0Session5DataStructuresandAlgorithmsSelectaPivot.arr210435546382816898330567PivotImplementingQuickSortAlgorithm(Contd.)Ver.1.0Session5DataStructuresandAlgorithmsStartfromtheleftendofthelist(atindex1).Moveinthelefttorightdirection.Searchforthefirstelementthatisgreaterthanthepivotvalue.arr210435546382816898330567PivotGreaterelementGreaterValueImplementingQuickSortAlgorithm(Contd.)Ver.1.0Session5DataStructuresandAlgorithmsStartfromtherightendofthelist.Moveintherighttoleftdirection.Searchforthefirstelementthatissmallerthanorequaltothepivotvalue.210435546382816898330567SmallerelementSmallerValueImplementingQuickSortAlgorithm(Contd.)arrPivotGreaterValueVer.1.0Session5DataStructuresandAlgorithmsInterchangethegreatervaluewithsmallervalue.arr210435546382816898330567PivotGreaterValueSmallerValueSwap5516ImplementingQuickSortAlgorithm(Contd.)Ver.1.0Session5DataStructuresandAlgorithmsContinuethesearchforanelementgreaterthanthepivot.Startfromarr[2]andmoveinthelefttorightdirection.Searchforthefirstelementthatisgreaterthanthepivotvalue.arr210431646382855898330567PivotGreaterelementGreaterValueImplementingQuickSortAlgorithm(Contd.)Ver.1.0Session5DataStructuresandAlgorithmsContinuethesearchforanelementsmallerthanthepivot.Startfromarr[3]andmoveintherighttoleftdirection.Searchforthefirstelementthatissmallerthanorequaltothepivotvalue.210431646382855898330567PivotSmallerelementSmallerValueGreaterValueImplementingQuickSortAlgorithm(Contd.)arrVer.1.0Session5DataStructuresandAlgorithmsThesmallervalueisonthelefthandsideofthegreatervalue.Valuesremainsame.ImplementingQuickSortAlgorithm(Contd.)210431646382855898330567PivotSmallerValueGreaterValuearrVer.1.0Session5DataStructuresandAlgorithmsListisnowpartitionedintotwosublists.List1containsallvalueslessthanorequaltothepivot.List2containsallthevaluesgreaterthanthepivot.ImplementingQuickSortAlgorithm(Contd.)2104316463855898330567Pivot2816List1List2558983304638arr2104356728Ver.1.0Session5DataStructuresandAlgorithmsReplacethepivotvaluewiththelastelementofList1.Thepivotvalue,28isnowplacedatitscorrectpositioninthelist.ImplementingQuickSortAlgorithm(Contd.)arr16List1List25589833038Swap2821043567462816Ver.1.0Session5DataStructuresandAlgorithmsTruncatethelastelement,thatis,pivotfromList1.ImplementingQuickSortAlgorithm(Contd.)List25589833038243567arrList1101628161616046Ver.1.0Session5DataStructuresandAlgorithmsList1hasonlyoneelement.Therefore,nosortingrequired.ImplementingQuickSortAlgorithm(Contd.)arr16List1List255898330381616024356746Ver.1.0Session5DataStructuresandAlgorithmsSortthesecondlist,List2.ImplementingQuickSortAlgorithm(Contd.)1655898330381616024356746List1List2arrVer.1.0Session5DataStructuresandAlgorithmsSelectapivot.Thepivotinthiscasewillbearr[2],thatis,46.ImplementingQuickSortAlgorithm(Contd.)16558983303816160Pivot24356746List1List2arrVer.1.0Session5DataStructuresandAlgorithmsImplementingQuickSortAlgorithm(Contd.)16558983303816160PivotStartfromtheleftendofthelist(atindex3).Moveinthelefttorightdirection.Searchforthefirstelementthatisgreaterthanthepivotvalue.GreaterelementGreaterValue24356746List1List2arrVer.1.0Session5DataStructuresandAlgorithmsImplementingQuickSortAlgorithm(Contd.)16558983303816160PivotGreaterValueStartfromtherightendofthelist(atindex7).Moveintherighttoleftdirection.Searchforthefirstelementthatissmallerthanorequaltothepivotvalue.SmallerelementSmallerValue24356746List1List2arrVer.1.0Session5DataStructuresandAlgorithmsImplementingQuickSortAlgorithm(Contd.)16558983303816160PivotGreaterValueSmallerValueInterchangethegreatervaluewithsmallervalue.Swap305524356746List1List2arrVer.1.0Session5DataStructuresandAlgorithmsImplementingQuickSortAlgorithm(Contd.)1689833816160PivotContinuethesearchforanelementg