Bubble Sort in Python - Stack Abuse

In the most inefficient approach, Bubble Sort goes through n-1 iterations, looking at n-1 pairs of adjacent elements. This gives it the time ... SALogotypeArticlesLearnWritewithUsSigninSignupPythonJavaScriptJavaHomeArticlesBubbleSortinPythonOliveraPopovićIntroduction Formostpeople,BubbleSortislikelythefirstsortingalgorithmtheyheardofintheirComputerSciencecourse. It'shighlyintuitiveandeasyto"translate"intocode,whichisimportantfornewsoftwaredeveloperssotheycaneasethemselvesintoturningideasintoaformthatcanbeexecutedonacomputer.However,BubbleSortisoneoftheworst-performingsortingalgorithmsineverycaseexceptcheckingwhetherthearrayisalreadysorted,whereitoftenoutperformsmoreefficientsortingalgorithmslikeQuickSort. BubbleSort TheideabehindBubbleSortisverysimple,welookatpairsofadjacentelementsinanarray,onepairatatime,andswaptheirpositionsifthefirstelementislargerthanthesecond,orsimplymoveonifitisn't.Let'slookatanexampleandsortthearray8,5,3,1,4,7,9: Ifyoufocusonthefirstnumber,thenumber8,youcanseeit"bubblingup"thearrayintothecorrectplace.Then,thisprocessisrepeatedforthenumber5andsoon. Implementation Withthevisualizationoutoftheway,let'sgoaheadandimplementthealgorithm.Again,it'sextremelysimple: defbubble_sort(our_list): #Wegothroughthelistasmanytimesasthereareelements foriinrange(len(our_list)): #Wewantthelastpairofadjacentelementstobe(n-2,n-1) forjinrange(len(our_list)-1): ifour_list[j]>our_list[j+1]: #Swap our_list[j],our_list[j+1]=our_list[j+1],our_list[j] Now,let'spopulatealistandcallthealgorithmonit: our_list=[19,13,6,2,18,8] bubble_sort(our_list) print(our_list) Output: [2,6,8,13,18,19] Optimization Thesimpleimplementationdiditsjob,buttherearetwooptimizationswecanmakehere. Whennoswapsaremade,thatmeansthatthelistissorted.Though,withthepreviouslyimplementedalgorithm,it'llkeepevaluatingtherestofthelisteventhoughitreallydoesn'tneedto.Tofixthis,we'llkeepabooleanflagandcheckifanyswapsweremadeinthepreviousiteration. Ifnoswapsaremade,thealgorithmshouldstop: defbubble_sort(our_list): #Wewanttostoppassingthroughthelist #assoonaswepassthroughwithoutswappinganyelements has_swapped=True while(has_swapped): has_swapped=False foriinrange(len(our_list)-1): ifour_list[i]>our_list[i+1]: #Swap our_list[i],our_list[i+1]=our_list[i+1],our_list[i] has_swapped=True TheotheroptimizationwecanmakeleveragesthefactthatBubbleSortworksinsuchawaythatthelargestelementsinaparticulariterationendupattheendofthearray. Thefirsttimewepassthroughthelistthepositionnisguaranteedtobethelargestelement,thesecondtimewepassthroughthepositionn-1isguaranteedtobethesecond-largestelementandsoforth. Thismeansthatwitheachconsecutiveiterationwecanlookatonelesselementthanbefore.Moreprecisely,inthek-thiteration,onlyneedtolookatthefirstn-k+1elements: defbubble_sort(our_list): has_swapped=True num_of_iterations=0 while(has_swapped): has_swapped=False foriinrange(len(our_list)-num_of_iterations-1): ifour_list[i]>our_list[i+1]: #Swap our_list[i],our_list[i+1]=our_list[i+1],our_list[i] has_swapped=True num_of_iterations+=1 TimeComparison Let'sgoaheadandcomparethetimeittakesforeachofthesecodesnippetstosortthesamelistathousandtimesusingthetimeitmodule: FreeeBook:GitEssentialsCheckoutourhands-on,practicalguidetolearningGit,withbest-practices,industry-acceptedstandards,andincludedcheatsheet.StopGooglingGitcommandsandactuallylearnit!DownloadtheeBook UnoptimizedBubbleSorttook:0.0106407 BubbleSortwithabooleanflagtook:0.0078251 BubbleSortwithabooleanflagandshortenedlisttook:0.0075207 Thereisn'tmuchofadifferencebetweenthelattertwoapproachesduetothefactthatthelistisextremelyshort,butonlargerlists-thesecondoptimizationcanmakeahugedifference. Conclusion Inthemostinefficientapproach,BubbleSortgoesthroughn-1iterations,lookingatn-1pairsofadjacentelements.ThisgivesitthetimecomplexityofO(n2),inbothbest-caseandaverage-casesituations.O(n2)isconsideredprettyhorribleforasortingalgorithm. ItdoeshaveanO(1)spacecomplexity,butthatisn'tenoughtocompensateforitsshortcomingsinotherfields. However,it'sstillabigpartofthesoftwaredevelopmentcommunityandhistory,andtextbooksalmostneverfailtomentionitwhentalkingaboutbasicsortingalgorithms. #pythonLastUpdated:February10th,2020Wasthisarticlehelpful?Youmightalsolike...PythonDocstringsHandlingUnixSignalsinPythonTheBestMachineLearningLibrariesinPythonListsvsTuplesinPythonGuidetoSendingHTTPRequestsinPythonwithurllib3Improveyourdevskills!Gettutorials,guides,anddevjobsinyourinbox.EmailaddressSignUpNospamever.Unsubscribeatanytime.ReadourPrivacyPolicy.OliveraPopovićAuthorLinkedIn:https://rs.linkedin.com/in/227503161 Ifyouneedanyhelp-postitinthecomments:)ThatwaysomeoneelsecanreplyifI'mbusy. InthisarticleIntroductionBubbleSortImplementationOptimizationTimeComparisonConclusionFreeCourseGraphsinPython-TheoryandImplementation#python#datastructures#algorithms#computerscienceGraphsareanextremelyversatiledatastructure.Moresothanmostpeoplerealize!Graphscanbeusedtomodelpracticallyanything,giventheirnatureof...DetailsProjectDataVisualizationinPython:TheCollatzConjecture#python#matplotlib#datavisualizationTheCollatzConjectureisanotoriousconjectureinmathematics.Aconjectureisaconclusionbasedonexistingevidence-however,aconjecturecannotbeproven....DetailsTwitterGitHubFacebook©2013-2022StackAbuse.Allrightsreserved.DisclosurePrivacyTermsDonotsharemyPersonalInformation.