Bubble Sort – Algorithm, Source Code, Time Complexity

Best Case Time Complexity ArticleSeries:SortingAlgorithms Part1:Introduction Part2:SortinginJava Part3:InsertionSort Part4:SelectionSort Part5:BubbleSort Part6:Quicksort Part7:MergeSort Part8:Heapsort Part9:CountingSort Part10:RadixSort (SignupfortheHappyCodersNewslettertobeimmediatelyinformedaboutnewparts.) Thisarticleispartoftheseries"SortingAlgorithms:UltimateGuide"and... explainshowBubbleSortworks,presentstheBubbleSortsourcecode,explainshowtoderiveitstimecomplexityandcheckswhethertheperformanceoftheownimplementationcorrespondstotheexpectedruntimebehavioraccordingtothetimecomplexity. YoucanfindthesourcecodeforallarticlesinthisseriesinmyGitHub-Repository. Contents hide 1 BubbleSortAlgorithm 1.1 BubbleSortExample 1.2 OriginoftheName 2 BubbleSortJavaSourceCode 3 BubbleSortTimeComplexity 3.1 BestCaseTimeComplexity 3.2 WorstCaseTimeComplexity 3.3 AverageTimeComplexity 4 RuntimeoftheJavaBubbleSortExample 4.1 SwapandComparisonOperationsinAverageandWorstCase 4.2 WhyIsBubbleSortFasterforElementsSortedinDescendingOrderThanforUnsortedElements? 5 OtherCharacteristicsofBubbleSort 5.1 SpaceComplexityofBubbleSort 5.2 StabilityofBubbleSort 5.3 ParallelizabilityofBubbleSort 6 Summary BubbleSortAlgorithm WithBubbleSort(sometimes"Bubblesort"),twosuccessiveelementsarecomparedwitheachother,and–iftheleftelementislargerthantherightone–theyareswapped. Thesecomparisonandswapoperationsareperformedfromlefttorightacrossallelements.Therefore,afterthefirstpass,thelargestelementispositionedonthefarright.Orbetter: atthelatest afterthefirstpass–itmayhavearrivedtherebefore. Yourepeatthisprocessuntilthereisnomoreswappinginoneiteration. BubbleSortExample Inthefollowingvisualizations,Ishowhowtosortthearray[6,2,4,9,3,7]withBubbleSort: Preparation Wedividethearrayintoaleft,unsorted–andaright,sortedpart.Therightpartisemptyatthebeginning: Iteration1 Wecomparethefirsttwoelements,the6andthe2,andsincethe6issmaller,weswaptheelements: Nowwecomparethesecondwiththethirdelement,i.e.,the6withthe4.Thesearealsointhewrongorderandare,therefore,swapped: Wecomparethethirdwiththefourthelement,i.e.,the6withthe9.The6issmallerthanthe9,sowedonotneedtoswapthesetwoelements. Thefourthandfifthelement,the9andthe3,needtobeswappedagain: Andfinally,thefifthandsixthelements,the9andthe7,mustbeswapped.Afterthat,thefirstiterationisfinished. The9hasreacheditsfinalposition,andwemovetheborderbetweentheareasonefieldtotheleft: Inthenextiteration,thisboundaryshowsusuptowhichpositiontheelementshavetobecompared.Bytheway,theareaboundaryonlyexistsintheoptimizedversionofBubbleSort.Intheoriginalvariant,itismissing.Consequently,ineveryiteration,thecomparisonisperformedunnecessarilyuntiltheendofthearray. Iteration2 Westartagainatthebeginningofthearrayandcomparethe2withthe4.Theseareinthecorrectorderandneednotbeswapped. Thesameappliestothe4andthe6. The6andthe3,however,mustbeswappedtobeinthecorrectorder: The6andthe7areintherightorderanddonotneedtobeswapped.Wedonotneedtocomparefurthersincethe9isalreadyinthesortedarea. Finally,wemovetheareaboundaryonepositiontotheleftagainsothatwedon'thavetolookatthelasttwoelements,the7andthe9,anyfurther. Iteration3 Againwestartatthebeginningofthearray.The2andthe4arepositionedcorrectlytoeachother.The4andthe3mustbeswapped: The4andthe6donothavetobeswapped.The7andthe9arealreadysorted.Sothisiterationisalreadyfinished,andwemovetheareabordertotheleft: Iteration4 Westartagainatthebeginningofthearray.Intheunsortedarea,neitherthe2and3northe3and4havetobeswapped.Nowallelementsaresorted,andwecanfinishthealgorithm. OriginoftheName Whenweanimatethepreviousexample'sswappingoperations,theelementsgraduallyrisetotheirtargetpositions–similartobubbles,hencethename"BubbleSort": BubbleSortJavaSourceCode BelowyouwillfindtheoptimizedimplementationofBubbleSortdescribedabove. Inthefirstiteration,thelargestelementmovestothefarright.Intheseconditeration,thesecond-largestmovestothesecondlastposition.Andsoon.Therefore,ineveryiteration,wehavetocompareoneelementlessthaninthepreviousiteration. (Intheprevioussection'sexample,Ihadrepresentedthisbytheareaboundary,whichmovesonepositiontotheleftaftereachiteration.) Therefore,intheouterloop,wedecrementthevaluemax,startingatelements.length-1,byoneineveryiteration. Theinnerloopthencomparestwoelementswitheachotheruptothepositionmaxandswapsthemiftheleftelementislargerthantherightone. Ifnoelementswereswappedinaniteration(i.e.,swappedisfalse),thealgorithmendsprematurely. publicclassBubbleSortOpt1{ publicstaticvoidsort(int[]elements){ for(intmax=elements.length-1;max>0;max--){ booleanswapped=false; for(inti=0;iright){ elements[i+1]=left; elements[i]=right; swapped=true; } } if(!swapped)break; } } }Codelanguage:Java(java) ThecodeshownisslightlydifferentfromtheBubbleSortOpt1classintheGitHubrepository.TheclassintherepositoryimplementstheSortAlgorithminterfacetobeinterchangeablewithinthetestframework. Thenon-optimizedalgorithm–whichcomparestheelementsuntiltheendineachiteration–canbefoundintheclassBubbleSort. IntheclassBubbleSortOpt2,youfindatheoreticallyevenmoreoptimizedalgorithm.Afterthenthiteration,itispossiblethatnotonlythelastnelementsaresorted,butmorethanthat–dependingonhowtheelementswereoriginallyarranged. Therefore,thisvariantdoesnotcountmaxdownby1,but,aftereachiteration,setsmaxtothepositionofthelastswappedelement.However,theCompareBubbleSortstestshowsthatthisvariantisslowerinpractice: -----Resultsafter50iterations----- BubbleSort->fastest:772.6ms,median:790.3ms BubbleSortOpt1->fastest:443.2ms,median:452.7ms BubbleSortOpt2->fastest:497.0ms,median:510.0msCodelanguage:plaintext(plaintext) YoucanfindthecompleteoutputofthetestprograminthefileTestResults_BubbleSort_Algorithms.log. Whyisthesecondoptimizedversionslower?Iassumeit'sbecausesavingandrepeatedly(withinoneiteration)updatingthelastswappedelement'spositionismuchmoreexpensivethanchangingtheswappedvalueonlyonce(periteration). BubbleSortTimeComplexity Wedenotebynthenumberofelementstobesorted.Intheexampleabove,n=6. Thetwonestedloopssuggestthatwearedealingwithquadratictime,i.e.,atimecomplexity*ofO(n²).Thiswillbethecaseifbothloopsiteratetoavaluethatgrowslinearlywithn. ForBubbleSort,thisisnotaseasytoproveasforInsertionSortorSelectionSort. WithBubbleSort,wehavetoexaminebest,worse,andaveragecaseseparately.Wewilldothisinthefollowingsubsections. *Iexplaintheterms"timecomplexity"and"bigOnotation"inthisarticleusingexamplesanddiagrams. BestCaseTimeComplexity Let'sstartwiththemoststraightforwardcase:Ifthenumbersarealreadysortedinascendingorder,thealgorithmwilldetermineinthefirstiterationthatnonumberpairsneedtobeswappedandwillthenterminateimmediately. Thealgorithmmustperformn-1comparisons;therefore: Thebest-casetimecomplexityofBubbleSortis:O(n) WorstCaseTimeComplexity Iwilldemonstratetheworstcasewithanexample.Let'sassumewewanttosortthedescendingarray[6,5,4,3,2,1]withBubbleSort. Inthefirstiteration,thelargestelement,the6,movesfromfarlefttofarright.Iomittedthefivesinglesteps(swappingthepairs6/5,6/4,6/3,6/2,6/1)inthefigure: Intheseconditeration,thesecondlargestelement,the5,ismovedfromthefarleft–viafourintermediatesteps–tothesecondlastposition: Inthethirditeration,the4ispushedtothethirdlastplace–viathreeintermediatesteps. Inthefourthiteration,the3ismoved–viatwosinglesteps–toitsfinalposition: Andfinally,the2andthe1areswapped: Sointotalwehave5+4+3+2+1=15comparisonandexchangeoperations. Wecanalsocalculatethisasfollows: Sixelementstimesfivecomparisonandexchangeoperations;dividedbytwo,sinceonaverageacrossalliterations,halfoftheelementsarecomparedandswapped: 6×5×½ = 30×½ = 15 Ifwereplace6withn,weget: n×(n–1)×½ Whenmultiplied,thatgivesus: ½ (n²–n) Thehighestpowerofninthistermisn²;therefore: Theworst-casetimecomplexityofBubbleSortis:O(n²) AverageTimeComplexity Unfortunately,theaveragetimecomplexityofBubbleSortcannot–incontrasttomostothersortingalgorithms–beexplainedinanillustrativeway. Withoutprovingthismathematically(thiswouldgobeyondthescopeofthisarticle),onecanroughlysaythatintheaveragecase,onehasabouthalfasmanyexchangeoperationsasintheworstcasesinceabouthalfoftheelementsareinthecorrectpositioncomparedtotheneighboringelement.Sothenumberofexchangeoperationsis: ¼ (n²–n) Itbecomesevenmorecomplicatedwiththenumberofcomparisonoperations,whichamountsto(source:thisGermanWikipediaarticle;theEnglishversiondoesn'tcoverthis): ½(n²-n×ln(n)-(𝛾+ln(2)-1)×n)+O(√n) Inbothterms,thehighestpowerofnisagainn²;therefore: TheaveragetimecomplexityofBubbleSortcaseis:O(n²) RuntimeoftheJavaBubbleSortExample Let'sverifythetheorywithatest!IntheGitHubrepository,you'llfindtheUltimateTestprogramthattestsBubbleSort(andalltheothersortingalgorithmspresentedinthisseriesofarticles)usingthefollowingcriteria: forarraysizesstartingfrom1,024elements,doublingaftereachiterationuntilwereachanarraysizeof536,870,912(=229)orthesortingprocesstakeslongerthan20seconds;forunsorted,ascendinganddescendingpresortedelements;withtwowarm-uproundstogivetheHotSpotcompilerenoughtimetooptimizethecode. Thewholeprocedureisrepeateduntilweaborttheprogram.Aftereachiteration,theprogramdisplaysthemedianofallpreviousmeasurementresults. HereistheresultforBubbleSortafter50iterations: nunsorteddescendingascending............8,19261.73ms35.18ms0.004ms16,384294.64ms141.16ms0.008ms32,7681,272.07ms566.39ms0.015ms65,5365,196.82ms2,267.85ms0.030ms131,07220,903.54ms9,068.25ms0.060ms262,144––0.129ms............536,870,912––192.509ms Thisisonlyanexcerpt;youcanfindthecompleteresulthere. Herearetheresultsagainasadiagram: Withascendingpresortedelements,BubbleSortissofastthatthecurvedoesnotshowanyupwarddeflection.Therefore,hereisthecurveoncemoreseparately: Youcanseeclearly: Theruntimeisapproximatelyquadrupledwhendoublingtheinputquantityforunsortedanddescendingsortedelements.Theruntimeforelementssortedinascendingorderincreaseslinearlyandisordersofmagnitudesmallerthanforunsortedelements.Theruntimeintheaveragecaseisslightlymorethantwiceashighasintheworstcase. Thefirsttwoobservationsmeetexpectations. Butwhyistheruntimeintheaveragecasesomuchhigherthanintheworstcase?Wouldn'twehavetohaveabouthalfasmanyswapoperationsthereandatleastminimallyfewercomparisons–andaccordinglyratherhalfthetimethantwice? SwapandComparisonOperationsinAverageandWorstCase Tocheckthis,IusetheprogramCountOperationstodisplaythenumberofdifferentoperations.I'vesummarizedtheresultsforunsortedanddescendingsortedelementsinthefollowingtable: nSwapsunsortedSwapsdescendingComparisonsunsortedComparisonsdescending...............1288,05016,2568,1368,25525631,85465,28032,89332,895512128,340261,632130,767131,3271,024528,0041,047,552524,475524,7992,0482,111,7604,192,2562,097,5462,098,175............... Theresultsconfirmtheassumption:Withunsortedelements,wehaveabouthalfasmanyswapoperationsandslightlyfewercomparisonsthanwithelementssortedindescendingorder. WhyIsBubbleSortFasterforElementsSortedinDescendingOrderThanforUnsortedElements? HowisitpossiblethatBubbleSortissomuchfasterwithelementssortedindescendingorderthanwithrandomlyorderedelementsdespitetwiceasmanyexchangeoperations? Thereasonforthisdiscrepancycanbefoundin"branchprediction": Iftheelementsaresortedindescendingorder,thentheresultofthecomparisonoperationif(left>right)isalwaystrueintheunsortedareaandalwaysfalseinthesortedarea. Ifthebranchpredictionassumesthattheresultofacomparisonisalwaysthesameasthatofthepreviouscomparison,thenitisalwaysrightwiththisassumption–withonesingleexception:attheareaboundary.ThisallowstheCPU'sinstructionpipelinetobefullyutilizedmostofthetime. Ontheotherhand,withunsorteddata,noreliablepredictionscanbemadeabouttheoutcomeofthecomparison,sothatthepipelinemustoftenbedeletedandrefilled. OtherCharacteristicsofBubbleSort Thissectiondealswiththespacecomplexity,stability,andparallelizabilityofBubbleSort. SpaceComplexityofBubbleSort BubbleSortrequiresnoadditionalmemoryspaceapartfromtheloopvariablemax,andtheauxiliaryvariablesswapped,left,andright. ThespacecomplexityofBubbleSortis,therefore,O(1). StabilityofBubbleSort Byalwayscomparingtwoadjacentelementswitheachother–andonlyswappingthemiftheleftelementislargerthantherightelement–elementswiththesamekeycanneverswappositionsrelativetoeachother. Thatwouldrequiretwoelementstoswapplacesacrossmorethanoneposition(asithappenswithSelectionSort).WithBubbleSort,thiscannotoccur. BubbleSortis,therefore,astablesortingalgorithm. ParallelizabilityofBubbleSort TherearetwoapproachestoparallelizeBubbleSort: Approach1"Odd-EvenSort" Youcompareinparallelthefirstwiththesecondelement,thethirdwiththefourth,thefifthwiththesixth,etc.andswaptherespectiveelementsiftheleftoneislargerthantherightone. Thenyoucomparethesecondelementwiththethird,thefourthwiththefifth,thesixthwiththeseventh,andsoon. Thesetwostepsarealternateduntilnomoreelementsareswappedineitherstep: Thisalgorithmisalsocalled"Odd-evensort". YoucanfindthesourcecodeintheBubbleSortParallelOddEvenclassintheGitHubrepository. Thesynchronizationbetweenthesteps(thethreadsmaynotstartwithastepuntilallthreadshavefinishedthepreviousstep)isrealizedwithaPhaser. Approach2"DivideandConquer" Youdividethearraytobesortedintoasmanyareas("partitions")asyouhaveCPUcoresavailable. NowyouperformoneBubbleSortiterationinallpartitionsinparallel.Waituntilallthreadsarefinished,andthencomparethelastelementofonepartitionwiththefirstofthenextpartition.Whenallthreadsarefinished,theprocessstartsagain. Repeatthesestepsuntilnomoreelementsareswappedinallthreads: YoucanfindthesourcecodeforthealgorithmintheBubbleSortParallelDivideAndConquerclassintheGitHubrepository. Again,aPhaserisusedtosynchronizethethreads.Infact,muchofthecodeofbothalgorithmsisthesame,sincethearrayisalsodividedintopartitionsfortheodd-evenapproach.ImovedthesharedcodetotheabstractbaseclassBubbleSortParallelSort. ParallelBubbleSort:Performance IcomparetheperformanceoftheparallelvariantswiththeCompareBubbleSortstestmentionedabove.Hereistheresultfortheparallelalgorithms,comparedtothefastestsequentialvariant -----Resultsafter50iterations----- BubbleSortOpt1->fastest:443.2ms,median:452.7ms BubbleSortParallelOddEven->fastest:62.6ms,median:68.6ms BubbleSortParallelDivideAndConquer->fastest:126.8ms,median:145.7msCodelanguage:plaintext(plaintext) The"odd-even"variantisonmy6-coreCPU(12virtualcoreswithHyper-threading)andwith20,000unsortedelementsthus6.6timesfasterthanthesequentialversion. The"divide-and-conquer"approachisonly3.1timesfaster.Thisisprobablybecauseeachthreadonlyperformsonecomparisoninthesecondsub-stepoftheiteration.Thisstandsincontrasttotherelativelyhighsynchronizationeffortrequiredbythephaser. Summary BubbleSortisaneasy-to-implement,stablesortingalgorithmwithatimecomplexityofO(n²)intheaverageandworstcases–andO(n)inthebestcase. Youwillfindmoresortingalgorithmsinthisoverviewofallsortingalgorithmsandtheircharacteristicsinthefirstpartofthearticleseries. BubbleSortwasthelastsimplesortingmethodofthisarticleseries;inthenextpart,wewillentertherealmofefficientsortingmethods,startingwithQuicksort. Ifyoulikedthearticle,feelfreetoshareitusingoneofthesharebuttonsattheend.WouldyoulikemetoinformeyoubyemailwhenIpublishanewarticle?ThenclickheretosubscribetotheHappyCodersnewsletter. Share Tweet Share Share AbouttheAuthorI'mafreelancesoftwaredeveloperwithmorethantwodecadesofexperienceinscalableJavaenterpriseapplications.Myfocusisonoptimizingcomplexalgorithmsandonadvancedtopicssuchasconcurrency,theJavamemorymodel,andgarbagecollection.HereonHappyCoders.eu,IwanttohelpyoubecomeabetterJavaprogrammer. Readmoreaboutmehere. LeaveaReplyCancelreplyYouremailaddresswillnotbepublished.Requiredfieldsaremarked*Comment*Name* Email* Youmightalsolikethefollowingarticles RadixSort–Algorithm,SourceCode,TimeComplexitySvenWoltmannJuly19,2022Stackvs.QueueSvenWoltmannJune8,2022JavaQueuevs.DequeSvenWoltmannJune7,2022JavaDequevs.StackSvenWoltmannJune7,2022 search