Bubble Sort Algorithm with Python using List Example - Guru99

Bubble Sort is a sorting algorithm used to sort list items in ascending order by comparing two adjacent values. If the first value is higher ... Skiptocontent WhatisaBubbleSort? BubbleSortisasortingalgorithmusedtosortlistitemsinascendingorderbycomparingtwoadjacentvalues.Ifthefirstvalueishigherthansecondvalue,thefirstvaluetakesthesecondvalueposition,whilesecondvaluetakesthefirstvalueposition.Ifthefirstvalueislowerthanthesecondvalue,thennoswappingisdone. Thisprocessisrepeateduntilallthevaluesinalisthavebeencomparedandswappedifnecessary.Eachiterationisusuallycalledapass.Thenumberofpassesinabubblesortisequaltothenumberofelementsinalistminusone. InthisBubbleSortinginPythontutorialyouwilllearn: WhatisaBubbleSort? ImplementingtheBubbleSortAlgorithm OptimizedBubbleSortAlgorithm VisualRepresentation PythonExamples CodeExplanation Bubblesortadvantages BubblesortDisadvantages ComplexityAnalysisofBubbleSort ImplementingtheBubbleSortAlgorithm Wewillbreakdowntheimplementationintothree(3)steps,namelytheproblem,thesolution,andthealgorithmthatwecanusetowritecodeforanylanguage. Theproblem Alistofitemsisgiveninrandomorder,andwewouldliketoarrangetheitemsinanorderlymanner Considerthefollowinglist: [21,6,9,33,3] Thesolution Iteratethroughthelistcomparingtwoadjacentelementsandswappingthemifthefirstvalueishigherthanthesecondvalue. Theresultshouldbeasfollows: [3,6,9,21,33] Algorithm Thebubblesortalgorithmworksasfollows Step1)Getthetotalnumberofelements.Getthetotalnumberofitemsinthegivenlist Step2)Determinethenumberofouterpasses(n–1)tobedone.Itslengthislistminusone Step3)Performinnerpasses(n–1)timesforouterpass1.Getthefirstelementvalueandcompareitwiththesecondvalue.Ifthesecondvalueislessthanthefirstvalue,thenswapthepositions Step4)Repeatstep3passesuntilyoureachtheouterpass(n–1).Getthenextelementinthelistthenrepeattheprocessthatwasperformedinstep3untilallthevalueshavebeenplacedintheircorrectascendingorder. Step5)Returntheresultwhenallpasseshavebeendone.Returntheresultsofthesortedlist Step6)OptimizeAlgorithm Avoidunnecessaryinnerpassesifthelistoradjacentvaluesarealreadysorted.Forexample,iftheprovidedlistalreadycontainselementsthathavebeensortedinascendingorder,thenwecanbreaktheloopearly. OptimizedBubbleSortAlgorithm Bydefault,thealgorithmforbubblesortinPythoncomparesallitemsinthelistregardlessofwhetherthelistisalreadysortedornot.Ifthegivenlistisalreadysorted,comparingallvaluesisawasteoftimeandresources. Optimizingthebubblesorthelpsustoavoidunnecessaryiterationsandsavetimeandresources. Forexample,ifthefirstandseconditemsarealreadysorted,thenthereisnoneedtoiteratethroughtherestofthevalues.Theiterationisterminated,andthenextoneisinitiateduntiltheprocessiscompletedasshowninthebelowBubbleSortexample. Optimizationisdoneusingthefollowingsteps Step1)Createaflagvariablethatmonitorsifanyswappinghasoccurredintheinnerloop Step2)Ifthevalueshaveswappedpositions,continuetothenextiteration Step3)Ifthebenefitshavenotswappedpositions,terminatetheinnerloop,andcontinuewiththeouterloop. Anoptimizedbubblesortismoreefficientasitonlyexecutesthenecessarystepsandskipsthosethatarenotrequired. VisualRepresentation Givenalistoffiveelements,thefollowingimagesillustratehowthebubblesortiteratesthroughthevalueswhensortingthem Thefollowingimageshowstheunsortedlist FirstIteration Step1) Thevalues21and6arecomparedtocheckwhichoneisgreaterthantheother. 21isgreaterthan6,so21takesthepositionoccupiedby6while6takesthepositionthatwasoccupiedby21 Ourmodifiedlistnowlooksliketheoneabove. Step2) Thevalues21and9arecompared. 21isgreaterthan9,soweswapthepositionsof21and9 Thenewlistisnowasabove Step3) Thevalues21and33arecomparedtofindthegreaterone. Thevalue33isgreaterthan21,sonoswappingtakesplace. Step4) Thevalues33and3arecomparedtofindthegreaterone. Thevalue33isgreaterthan3,soweswaptheirpositions. Thesortedlistattheendofthefirstiterationisliketheoneabove SecondIteration Thenewlistaftertheseconditerationisasfollows ThirdIteration Thenewlistafterthethirditerationisasfollows FourthIteration Thenewlistafterthefourthiterationisasfollows PythonExamples ThefollowingcodeshowshowtoimplementtheBubbleSortalgorithminPython. defbubbleSort(theSeq): n=len(theSeq) foriinrange(n-1): flag=0 forjinrange(n-1): iftheSeq[j]>theSeq[j+1]: tmp=theSeq[j] theSeq[j]=theSeq[j+1] theSeq[j+1]=tmp flag=1 ifflag==0: break returntheSeq el=[21,6,9,33,3] result=bubbleSort(el) print(result) ExecutingtheabovebubblesortprograminPythonproducesthefollowingresults [6,9,21,3,33] CodeExplanation TheexplanationforthePythonBubbleSortprogramcodeisasfollows HERE, DefinesafunctionbubbleSortthatacceptsaparametertheSeq.Thecodedoesnotoutputanything. Getsthelengthofthearrayandassignsthevaluetoavariablen.Thecodedoesnotoutputanything Startsaforloopthatrunsthebubblesortalgorithm(n–1)times.Thisistheouterloop.Thecodedoesnotoutputanything Definesaflagvariablethatwillbeusedtodetermineifaswaphasoccurredornot.Thisisforoptimizationpurposes.Thecodedoesnotoutputanything Startstheinnerloopthatcomparesallthevaluesinthelistfromthefirsttothelastone.Thecodedoesnotoutputanything. Usestheifstatementtocheckifthevalueontheleft-handsideisgreaterthantheoneontheimmediaterightside.Thecodedoesnotoutputanything. AssignsthevalueoftheSeq[j]toatemporalvariabletmpiftheconditionevaluatestotrue.Thecodedoesnotoutputanything ThevalueoftheSeq[j+1]isassignedtothepositionoftheSeq[j].Thecodedoesnotoutputanything ThevalueofthevariabletmpisassignedtopositiontheSeq[j+1].Thecodedoesnotoutputanything Theflagvariableisassignedthevalue1toindicatethataswaphastakenplace.Thecodedoesnotoutputanything Usesanifstatementtocheckifthevalueofthevariableflagis0.Thecodedoesnotoutputanything Ifthevalueis0,thenwecallthebreakstatementthatstepsoutoftheinnerloop. ReturnsthevalueoftheSeqafterithasbeensorted.Thecodeoutputsthesortedlist. Definesavariableelthatcontainsalistofrandomnumbers.Thecodedoesnotoutputanything. AssignsthevalueofthefunctionbubbleSorttoavariableresult. Printsthevalueofthevariableresult. Bubblesortadvantages Thefollowingaresomeoftheadvantagesofthebubblesortalgorithm Itiseasytounderstand Itperformsverywellwhenthelistisalreadyoralmostsorted Itdoesnotrequireextensivememory. Itiseasytowritethecodeforthealgorithm Thespacerequirementsareminimalcomparedtoothersortingalgorithms. BubblesortDisadvantages Thefollowingaresomeofthedisadvantagesofthebubblesortalgorithm Itdoesnotperformwellwhensortinglargelists.Ittakestoomuchtimeandresources. It’smostlyusedforacademicpurposesandnotthereal-worldapplication. Thenumberofstepsrequiredtosortthelistisoftheordern2 ComplexityAnalysisofBubbleSort TherearethreetypesofComplexityare: 1)Sortcomplexity Thesortcomplexityisusedtoexpresstheamountofexecutiontimesandspacethatittakestosortthelist.Thebubblesortmakes(n–1)iterationstosortthelistwherenisthetotalnumberofelementsinthelist. 2)Timecomplexity ThetimecomplexityofthebubblesortisO(n2) Thetimecomplexitiescanbecategorizedas: Worstcase–thisiswherethelistprovidedisindescendingorder.Thealgorithmperformsthemaximumnumberofexecutionswhichisexpressedas[Big-O]O(n2) Bestcase–thisoccurswhentheprovidedlistisalreadysorted.Thealgorithmperformstheminimumnumberofexecutionswhichisexpressedas[Big-Omega]Ω(n) Averagecase–thisoccurswhenthelistisinrandomorder.TheaverageComplexityisrepresentedas[Big-theta]⊝(n2) 3)Spacecomplexity Thespacecomplexitymeasurestheamountofextraspacethatisneededforsortingthelist.Thebubblesortonlyrequiresone(1)extraspaceforthetemporalvariableusedforswappingvalues.Therefore,ithasaspacecomplexityofO(1). Summary Thebubblesortalgorithmworksbycomparingtwoadjacentvaluesandswappingthemifthevalueontheleftislessthanthevalueontheright. ImplementingabubblesortalgorithmisrelativelystraightforwardwithPython.Allyouneedtouseareforloopsandifstatements. Theproblemthatthebubblesortalgorithmsolvesistakingarandomlistofitemsandturningitintoanorderedlist. Thebubblesortalgorithmindatastructureperformsbestwhenthelistisalreadysortedasitperformsaminimalnumberofiterations. Thebubblesortalgorithmdoesnotperformwellwhenthelistisinreverseorder. ThebubblersorthasatimecomplexityofO(n2)andaspacecomplexityofO(1) Thebubblersortalgorithmisbestsuitedforacademicpurposesandnotreal-worldapplications. Theoptimizedbubblesortmakesthealgorithmmoreefficientbyskippingunnecessaryiterationswhencheckingvaluesthathavealreadybeensorted. YouMightLike: ArrayinDataStructure:Whatis,ArraysOperations[Examples] BFSVs.DFS:KnowtheDifferencewithExample HashTableinDataStructure:PythonExample TreeTraversals(Inorder,Preorder,Postorder):C,Python,C++Examples CombinationAlgorithm:PrintallPossibleCombinationsofR Postnavigation ReportaBug Previous PrevNextContinue Scrolltotop ToggleMenuClose Searchfor: Search