Bubble sort - Wikipedia

Pseudocode implementation Bubblesort FromWikipedia,thefreeencyclopedia Jumptonavigation Jumptosearch Simplecomparisonsortingalgorithm Thisarticleneedsadditionalcitationsforverification.Pleasehelpimprovethisarticlebyaddingcitationstoreliablesources.Unsourcedmaterialmaybechallengedandremoved.Findsources: "Bubblesort" – news ·newspapers ·books ·scholar ·JSTOR(November2016)(Learnhowandwhentoremovethistemplatemessage) BubblesortStaticvisualizationofbubblesort[1]ClassSortingalgorithmDatastructureArrayWorst-caseperformance O ( n 2 ) {\displaystyleO(n^{2})} comparisons, O ( n 2 ) {\displaystyleO(n^{2})} swapsBest-caseperformance O ( n ) {\displaystyleO(n)} comparisons, O ( 1 ) {\displaystyleO(1)} swapsAverageperformance O ( n 2 ) {\displaystyleO(n^{2})} comparisons, O ( n 2 ) {\displaystyleO(n^{2})} swapsWorst-casespacecomplexity O ( n ) {\displaystyleO(n)} total, O ( 1 ) {\displaystyleO(1)} auxiliary Bubblesort,sometimesreferredtoassinkingsort,isasimplesortingalgorithmthatrepeatedlystepsthroughthelist,comparesadjacentelementsandswapsthemiftheyareinthewrongorder.Thepassthroughthelistisrepeateduntilthelistissorted.Thealgorithm,whichisacomparisonsort,isnamedforthewaysmallerorlargerelements"bubble"tothetopofthelist. Thissimplealgorithmperformspoorlyinrealworlduseandisusedprimarilyasaneducationaltool.Moreefficientalgorithmssuchasquicksort,timsort,ormergesortareusedbythesortinglibrariesbuiltintopopularprogramminglanguagessuchasPythonandJava.[2][3] Contents 1Analysis 1.1Performance 1.2RabbitsandTurtles 1.3Step-by-stepexample 2Implementation 2.1Pseudocodeimplementation 2.2Optimizingbubblesort 3Use 4Variations 5Debateovername 6Inpopularculture 7Notes 8References 9Externallinks Analysis[edit] Anexampleofbubblesort.Startingfromthebeginningofthelist,compareeveryadjacentpair,swaptheirpositioniftheyarenotintherightorder(thelatteroneissmallerthantheformerone).Aftereachiteration,onelesselement(thelastone)isneededtobecompareduntiltherearenomoreelementslefttobecompared. Performance[edit] Bubblesorthasaworst-caseandaveragecomplexityof O ( n 2 ) {\displaystyleO(n^{2})} ,where n {\displaystylen} isthenumberofitemsbeingsorted.Mostpracticalsortingalgorithmshavesubstantiallybetterworst-caseoraveragecomplexity,often O ( n log ⁡ n ) {\displaystyleO(n\logn)} .Evenother O ( n 2 ) {\displaystyleO(n^{2})} sortingalgorithms,suchasinsertionsort,generallyrunfasterthanbubblesort,andarenomorecomplex.Forthisreason,bubblesortisrarelyusedinpractice. Likeinsertionsort,bubblesortisadaptive,givingitanadvantageoveralgorithmslikequicksort.Thismeansthatitmayoutperformthosealgorithmsincaseswherethelistisalreadymostlysorted(havingasmallnumberofinversions),despitethefactthatithasworseaverage-casetimecomplexity.Forexample,bubblesortis O ( n ) {\displaystyleO(n)} onalistthatisalreadysorted,whilequicksortwouldstillperformitsentire O ( n log ⁡ n ) {\displaystyleO(n\logn)} sortingprocess. Whileanysortingalgorithmcanbemade O ( n ) {\displaystyleO(n)} onapresortedlistsimplybycheckingthelistbeforethealgorithmruns,improvedperformanceonalmost-sortedlistsishardertoreplicate. RabbitsandTurtles[edit] Thedistanceanddirectionthatelementsmustmoveduringthesortdeterminebubblesort'sperformancebecauseelementsmoveindifferentdirectionsatdifferentspeeds.Anelementthatmustmovetowardtheendofthelistcanmovequicklybecauseitcantakepartinsuccessiveswaps.Forexample,thelargestelementinthelistwillwineveryswap,soitmovestoitssortedpositiononthefirstpassevenifitstartsnearthebeginning.Ontheotherhand,anelementthatmustmovetowardthebeginningofthelistcannotmovefasterthanonestepperpass,soelementsmovetowardthebeginningveryslowly.Ifthesmallestelementisattheendofthelist,itwilltake n − 1 {\displaystylen-1} passestomoveittothebeginning.Thishasledtothesetypesofelementsbeingnamedrabbitsandturtles,respectively,afterthecharactersinAesop'sfableofTheTortoiseandtheHare. Variouseffortshavebeenmadetoeliminateturtlestoimproveuponthespeedofbubblesort.Cocktailsortisabi-directionalbubblesortthatgoesfrombeginningtoend,andthenreversesitself,goingendtobeginning.Itcanmoveturtlesfairlywell,butitretains O ( n 2 ) {\displaystyleO(n^{2})} worst-casecomplexity.Combsortcompareselementsseparatedbylargegaps,andcanmoveturtlesextremelyquicklybeforeproceedingtosmallerandsmallergapstosmoothoutthelist.Itsaveragespeediscomparabletofasteralgorithmslikequicksort. Step-by-stepexample[edit] Takeanarrayofnumbers"51428",andsortthearrayfromlowestnumbertogreatestnumberusingbubblesort.Ineachstep,elementswritteninboldarebeingcompared.Threepasseswillberequired; FirstPass (51428)→(15428),Here,algorithmcomparesthefirsttwoelements,andswapssince5>1. (15428)→(14528),Swapsince5>4 (14528)→(14258),Swapsince5>2 (14258)→(14258),Now,sincetheseelementsarealreadyinorder(8>5),algorithmdoesnotswapthem. SecondPass (14258)→(14258) (14258)→(12458),Swapsince4>2 (12458)→(12458) (12458)→(12458) Now,thearrayisalreadysorted,butthealgorithmdoesnotknowifitiscompleted.Thealgorithmneedsoneadditionalwholepasswithoutanyswaptoknowitissorted. ThirdPass (12458)→(12458) (12458)→(12458) (12458)→(12458) (12458)→(12458) Implementation[edit] Pseudocodeimplementation[edit] Inpseudocodethealgorithmcanbeexpressedas(0-basedarray): procedurebubbleSort(A:listofsortableitems) n:=length(A) repeat swapped:=false fori:=1ton-1inclusivedo /*ifthispairisoutoforder*/ ifA[i-1]>A[i]then /*swapthemandremembersomethingchanged*/ swap(A[i-1],A[i]) swapped:=true endif endfor untilnotswapped endprocedure Optimizingbubblesort[edit] Thebubblesortalgorithmcanbeoptimizedbyobservingthatthen-thpassfindsthen-thlargestelementandputsitintoitsfinalplace.So,theinnerloopcanavoidlookingatthelastn−1itemswhenrunningforthen-thtime: procedurebubbleSort(A:listofsortableitems) n:=length(A) repeat swapped:=false fori:=1ton-1inclusivedo ifA[i-1]>A[i]then swap(A[i-1],A[i]) swapped:=true endif endfor n:=n-1 untilnotswapped endprocedure Moregenerally,itcanhappenthatmorethanoneelementisplacedintheirfinalpositiononasinglepass.Inparticular,aftereverypass,allelementsafterthelastswaparesorted,anddonotneedtobecheckedagain.Thisallowstoskipovermanyelements,resultinginaboutaworstcase50%improvementincomparisoncount(thoughnoimprovementinswapcounts),andaddsverylittlecomplexitybecausethenewcodesubsumesthe"swapped"variable: Toaccomplishthisinpseudocode,thefollowingcanbewritten: procedurebubbleSort(A:listofsortableitems) n:=length(A) repeat newn:=0 fori:=1ton-1inclusivedo ifA[i-1]>A[i]then swap(A[i-1],A[i]) newn:=i endif endfor n:=newn untiln≤1 endprocedure Alternatemodifications,suchasthecocktailshakersortattempttoimproveonthebubblesortperformancewhilekeepingthesameideaofrepeatedlycomparingandswappingadjacentitems. Use[edit] Bubblesort.ThelistwasplottedinaCartesiancoordinatesystem,witheachpoint(x,y)indicatingthatthevalueyisstoredatindexx.Thenthelistwouldbesortedbybubblesortaccordingtoeverypixel'svalue.Notethatthelargestendgetssortedfirst,withsmallerelementstakinglongertomovetotheircorrectpositions. Althoughbubblesortisoneofthesimplestsortingalgorithmstounderstandandimplement,itsO(n2)complexitymeansthatitsefficiencydecreasesdramaticallyonlistsofmorethanasmallnumberofelements.EvenamongsimpleO(n2)sortingalgorithms,algorithmslikeinsertionsortareusuallyconsiderablymoreefficient. Duetoitssimplicity,bubblesortisoftenusedtointroducetheconceptofanalgorithm,orasortingalgorithm,tointroductorycomputersciencestudents.However,someresearcherssuchasOwenAstrachanhavegonetogreatlengthstodisparagebubblesortanditscontinuedpopularityincomputerscienceeducation,recommendingthatitnolongerevenbetaught.[4] TheJargonFile,whichfamouslycallsbogosort"thearchetypical[sic]perverselyawfulalgorithm",alsocallsbubblesort"thegenericbadalgorithm".[5]DonaldKnuth,inTheArtofComputerProgramming,concludedthat"thebubblesortseemstohavenothingtorecommendit,exceptacatchynameandthefactthatitleadstosomeinterestingtheoreticalproblems",someofwhichhethendiscusses.[6] Bubblesortisasymptoticallyequivalentinrunningtimetoinsertionsortintheworstcase,butthetwoalgorithmsdiffergreatlyinthenumberofswapsnecessary.ExperimentalresultssuchasthoseofAstrachanhavealsoshownthatinsertionsortperformsconsiderablybetterevenonrandomlists.Forthesereasonsmanymodernalgorithmtextbooksavoidusingthebubblesortalgorithminfavorofinsertionsort. BubblesortalsointeractspoorlywithmodernCPUhardware.Itproducesatleasttwiceasmanywritesasinsertionsort,twiceasmanycachemisses,andasymptoticallymorebranchmispredictions.[citationneeded]ExperimentsbyAstrachansortingstringsinJavashowbubblesorttoberoughlyone-fifthasfastasaninsertionsortand70%asfastasaselectionsort.[4] Incomputergraphicsbubblesortispopularforitscapabilitytodetectaverysmallerror(likeswapofjusttwoelements)inalmost-sortedarraysandfixitwithjustlinearcomplexity(2n).Forexample,itisusedinapolygonfillingalgorithm,whereboundinglinesaresortedbytheirxcoordinateataspecificscanline(alineparalleltothexaxis)andwithincrementingytheirorderchanges(twoelementsareswapped)onlyatintersectionsoftwolines.Bubblesortisastablesortalgorithm,likeinsertionsort. Variations[edit] Odd–evensortisaparallelversionofbubblesort,formessagepassingsystems. Passescanbefromrighttoleft,ratherthanlefttoright.Thisismoreefficientforlistswithunsorteditemsaddedtotheend. Cocktailshakersortalternatesleftwardsandrightwardspasses. Ican'tbelieveitcansortisasortingalgorithmthatappearstobeanincorrectversionofbubblesort,butcanbeformallyproventoworkinawaymoreakintoinsertionsort.[7] Debateovername[edit] Bubblesorthasbeenoccasionallyreferredtoasa"sinkingsort".[8] Forexample,DonaldKnuthdescribestheinsertionofvaluesatortowardstheirdesiredlocationasletting"[thevalue]settletoitsproperlevel",andthat"thismethodofsortinghassometimesbeencalledthesiftingorsinkingtechnique.[9] Thisdebateisperpetuatedbytheeasewithwhichonemayconsiderthisalgorithmfromtwodifferentbutequallyvalidperspectives: Thelargervaluesmightberegardedasheavierandthereforebeseentoprogressivelysinktothebottomofthelist Thesmallervaluesmightberegardedaslighterandthereforebeseentoprogressivelybubbleuptothetopofthelist. Inpopularculture[edit] In2007,formerGoogleCEOEricSchmidtaskedthen-presidentialcandidateBarackObamaduringaninterviewaboutthebestwaytosortonemillionintegers;Obamapausedforamomentandreplied:"Ithinkthebubblesortwouldbethewrongwaytogo."[10][11] Notes[edit] ^Cortesi,Aldo(27April2007)."VisualisingSortingAlgorithms".Retrieved16March2017. ^"[JDK-6804124](coll)Replace"modifiedmergesort"injava.util.Arrays.sortwithtimsort-JavaBugSystem".bugs.openjdk.java.net.Retrieved2020-01-11. ^Peters,Tim(2002-07-20)."[Python-Dev]Sorting".Retrieved2020-01-11. ^abAstrachan,Owen(2003)."Bubblesort:anarchaeologicalalgorithmicanalysis"(PDF).ACMSIGCSEBulletin.35(1):1–5.doi:10.1145/792548.611918.ISSN 0097-8418. ^"jargon,node:bogo-sort". ^DonaldKnuth.TheArtofComputerProgramming,Volume3:SortingandSearching,SecondEdition.Addison-Wesley,1998.ISBN 0-201-89685-0.Pages106–110ofsection5.2.2:SortingbyExchanging."[A]lthoughthetechniquesusedinthecalculations[toanalyzethebubblesort]areinstructive,theresultsaredisappointingsincetheytellusthatthebubblesortisn'treallyverygoodatall.Comparedtostraightinsertion[…],bubblesortingrequiresamorecomplicatedprogramandtakesabouttwiceaslong!"(Quotefromthefirstedition,1973.) ^Fung,StanleyP.Y.(3October2021)."Isthisthesimplest(andmostsurprising)sortingalgorithmever?".arXiv:2110.01111[cs]. ^Black,PaulE.(24August2009)."bubblesort".DictionaryofAlgorithmsandDataStructures.NationalInstituteofStandardsandTechnology.Retrieved1October2014. ^Knuth,Donald.TheArtofComputerProgramming:Volume3:SearchingandSorting.p. 80.ISBN 0201896850. ^LaiStirland,Sarah(2007-11-14)."ObamaPassesHisGoogleInterview".Wired.Retrieved2020-10-27. ^BarackObama,EricSchmidt(Nov14,2007).BarackObama|CandidatesatGoogle(Youtube).MountainView,CA94043TheGoogleplex:TalksatGoogle.Eventoccursat23:20.Archivedfromtheoriginal(Video)onSeptember7,2019.RetrievedSep18,2019.{{citeAVmedia}}:CS1maint:location(link) References[edit] ThomasH.Cormen,CharlesE.Leiserson,RonaldL.Rivest,andCliffordStein.IntroductiontoAlgorithms,SecondEdition.MITPressandMcGraw-Hill,2001.ISBN 0-262-03293-7.Problem2-2,pg.40. SortinginthePresenceofBranchPredictionandCaches FundamentalsofDataStructuresbyEllisHorowitz,SartajSahniandSusanAnderson-FreedISBN 81-7371-605-6 OwenAstrachan.BubbleSort:AnArchaeologicalAlgorithmicAnalysis ComputerIntegratedManufacturingbySpasicPhD,SrdicMSc,OpenSource,1987.[1] Externallinks[edit] TheWikibookAlgorithmimplementationhasapageonthetopicof:Bubblesort WikimediaCommonshasmediarelatedtoBubblesort. WikiversityhaslearningresourcesaboutBubblesort Martin,DavidR.(2007)."AnimatedSortingAlgorithms:BubbleSort".Archivedfromtheoriginalon2015-03-03.–graphicaldemonstration "Lafore'sBubbleSort".(Javaappletanimation) OEISsequenceA008302(Table(statistics)ofthenumberofpermutationsof[n]thatneedkpair-swapsduringthesorting) vteSortingalgorithmsTheory Computationalcomplexitytheory BigOnotation Totalorder Lists Inplacement Stability Comparisonsort Adaptivesort Sortingnetwork Integersorting X+Ysorting Transdichotomousmodel Quantumsort Exchangesorts Bubblesort Cocktailshakersort Odd–evensort Combsort Gnomesort Proportionextendsort Quicksort Slowsort Stoogesort Bogosort Selectionsorts Selectionsort Heapsort Smoothsort Cartesiantreesort Tournamentsort Cyclesort Weak-heapsort Insertionsorts Insertionsort Shellsort Splaysort Treesort Librarysort Patiencesorting Mergesorts Mergesort Cascademergesort Oscillatingmergesort Polyphasemergesort Distributionsorts Americanflagsort Beadsort Bucketsort Burstsort Countingsort Interpolationsort Pigeonholesort Proxmapsort Radixsort Flashsort Concurrentsorts Bitonicsorter Batcherodd–evenmergesort Pairwisesortingnetwork Samplesort Hybridsorts Blockmergesort Kirkpatrick-Reischsort Timsort Introsort Spreadsort Merge-insertionsort Other Topologicalsorting Pre-topologicalorder Pancakesorting Spaghettisort Retrievedfrom"https://en.wikipedia.org/w/index.php?title=Bubble_sort&oldid=1096579961" Categories:SortingalgorithmsComparisonsortsStablesortsHiddencategories:CS1maint:locationArticleswithshortdescriptionShortdescriptionisdifferentfromWikidataArticlesneedingadditionalreferencesfromNovember2016AllarticlesneedingadditionalreferencesAllarticleswithunsourcedstatementsArticleswithunsourcedstatementsfromAugust2015CommonscategorylinkisonWikidataArticleswithexamplepseudocode Navigationmenu Personaltools NotloggedinTalkContributionsCreateaccountLogin Namespaces ArticleTalk English Views ReadEditViewhistory More Search Navigation MainpageContentsCurrenteventsRandomarticleAboutWikipediaContactusDonate Contribute HelpLearntoeditCommunityportalRecentchangesUploadfile Tools WhatlinkshereRelatedchangesUploadfileSpecialpagesPermanentlinkPageinformationCitethispageWikidataitem Print/export DownloadasPDFPrintableversion Inotherprojects WikimediaCommonsWikibooksWikiversity Languages العربيةAzərbaycancaবাংলাभोजपुरीБългарскиCatalàČeštinaDanskDeutschEestiΕλληνικάEspañolEsperantoفارسیFrançais한국어Հայերենहिन्दीÍslenskaItalianoעבריתქართულიҚазақшаKurdîLëtzebuergeschLietuviųLombardMagyarമലയാളംNederlands日本語NorskbokmålPolskiPortuguêsРусскийSimpleEnglishSlovenčinaSlovenščinaСрпски/srpskiSuomiSvenskaTagalogไทยTürkçeУкраїнськаTiếngViệt粵語中文 Editlinks