Best Case for Bubble Sort - algorithm - Stack Overflow

Bubble sort has worst-case and average complexity both О(n²), where n is the number of items being sorted. There exist many sorting algorithms ... Home Public Questions Tags Users Companies Collectives ExploreCollectives Teams StackOverflowforTeams –Startcollaboratingandsharingorganizationalknowledge. CreateafreeTeam WhyTeams? Teams CreatefreeTeam Collectives™onStackOverflow Findcentralized,trustedcontentandcollaboratearoundthetechnologiesyouusemost. Learnmore Teams Q&Aforwork Connectandshareknowledgewithinasinglelocationthatisstructuredandeasytosearch. Learnmore BestCaseforBubbleSort AskQuestion Asked 12years,11monthsago Modified 4years,11monthsago Viewed 56ktimes 10 2 Iwanttoknowwhatwillbethebestcaseforabubblesort?Theremaybeacasewhereintheremaybenoswappingforthesaylast2passesforexample.I'mdoingmyprograminClanguage. Supposeihaveanarrayof5elementsandigivetheelementsas12543thentherewouldbenochangeinthelast2passes? algorithmbubble-sort Share Follow editedAug31,2009at17:26 HenkHolterman 253k3030goldbadges313313silverbadges497497bronzebadges askedAug31,2009at17:13 YashYash 2 1 ThebestcasewouldbeifthelistwerealreadysortedbutIdon'tthinkthat'swhatyou'reasking.Couldyoubemorespecific? – Dinah Aug31,2009at17:16 Ialsodon'tseewhatthishastodowithC# – MarcBollinger Aug31,2009at17:23 Addacomment  |  9Answers 9 Sortedby: Resettodefault Highestscore(default) Trending(recentvotescountmore) Datemodified(newestfirst) Datecreated(oldestfirst) 30 Bestcasescenarioisonepass.Thelistwouldalreadybesorted. Noswap=done. Share Follow answeredAug31,2009at17:14 jgallantjgallant 11k11goldbadge3737silverbadges7272bronzebadges 4 @JonWithoutspecifyingthealgorithmhowcouldyoutellaboutthebestcasecomplexity.Icouldseealotsofbubblesortimplementations – user567879 Jan31,2012at7:01 2 @user567879Regardlessofthebubblesortimplementation,atleastonefullpassisrequiredtoensurethelistissorted.Bestcaseisthelistissorted,andwillrequireasinglepasstoverifythis.en.wikipedia.org/wiki/Bubble_sort – jgallant Jan31,2012at10:27 @JonIfuseabubblesortlikethis(firstalgorithm)algorithmist.com/index.php/Bubble_sort.ThebestcasecomplexityisO(n^2)? – user567879 Feb1,2012at3:43 2 @user567879n^2wouldbeyourworstcase.Thinkaboutwhathappenswhenabubblesortisrun.IFyourlistisalreadysorted,itwillrunthroughyourlistonceforeachitem.BESTCASEisn(numberofitemsinthecollection),asabubblesortwillrequirecheckingeachitemonce. – jgallant Feb1,2012at10:31 Addacomment  |  26 BestCase:Thebestcasewouldbeifthelistwerealreadysorted. a)therewillbecomparisonsasitisbutnoexchangesandexecutiontimeisinO(n2) b)Butifwekeepatrackofexchangesineachpassandterminatetheprogramcheckingifnoexchanges.Thentheprogramwouldrequireonlyonepassandmax.(n-1)comparisonsarerequiredinthatsinglepassandwecansaythatthecomplexityisoforderofO(n). Share Follow answeredDec27,2009at8:49 user239103user239103 0 Addacomment  |  12 PleaseseeBubblesort: Bubblesorthasworst-caseandaverage complexitybothО(n²),wherenisthe numberofitemsbeingsorted.There existmanysortingalgorithmswith substantiallybetterworst-caseor averagecomplexityofO(nlogn).Even otherО(n²)sortingalgorithms,such asinsertionsort,tendtohavebetter performancethanbubblesort. Thereforebubblesortisnota practicalsortingalgorithmwhennis large. WorstcaseperformanceO(n²) BestcaseperformanceO(n) AveragecaseperformanceO(n²) WorstcasespacecomplexityO(n)total,O(1)auxiliary OptimalNo Share Follow editedAug31,2009at17:23 SamHarwell 95.5k1919goldbadges204204silverbadges272272bronzebadges answeredAug31,2009at17:15 AndrewHareAndrewHare 335k7171goldbadges633633silverbadges629629bronzebadges Addacomment  |  10 Therearemultiplewaystowritethebubblesortalgorithm,itseemslikeovertimethealgorithmhasgottenbetter,andmoreefficient.ThefirstbubblesortalgorithmIlearnedisbelow.ThealgorithmbelowBestandWorstCaseisO(n^2). BUBBLESORT(A) 1fori=1toA.length-1 2forj=A.lengthdowntoi+1 3ifA[j]A[i]then /*swapthemandremembersomethingchanged*/ swap(A[i-1],A[i]) swapped=true endif endfor untilnotswapped endprocedure HereisavideothathelpsexplainalittlebitaboutthefirstalgorithmintheCprogramminglanguage: https://youtu.be/qOpNrqqTsk4 Share Follow answeredAug12,2017at2:06 tempmailtempmail 16611silverbadge55bronzebadges 1 If,sayinsomeprogram,earlierbubblesortrequiredalliterationstobedone.Thisswapped=falsehelpsourprogramtostopanytimesoreducesmanysteps.wellanswer. – TahirHussainMir Aug12,2018at8:25 Addacomment  |  2 Thebestcaseiswhenthedataisalreadysorted.Anothergoodcaseiswhenthereareatinynumberofitemstosort-Ionceuseditwhenmytypicallistwastwoitemsandoccasionallywenttofour. Share Follow answeredAug31,2009at17:20 MarkRansomMarkRansom 288k4040goldbadges379379silverbadges604604bronzebadges Addacomment  |  1 It'shardtotellifyoumean Whatisthebestcasealgorithmiccomplexityofthebubblesort,inwhichcaseC#makesnodifference,theanswerisO(n)foranalreadysortedinput. When,ifever,youshouldconsiderusingabubblesort. Inthelattercase,youdon't,becauseforthesmallcasestheShellsortandInsertionsortwillbothoutperformit.SomeofthebestperformingsortingroutinesI'veseenarehybridsQuickSortthatuseaShellSortfor"small"sectionsofthearray. Share Follow answeredAug31,2009at17:19 SamHarwellSamHarwell 95.5k1919goldbadges204204silverbadges272272bronzebadges Addacomment  |  1 It'snotpossibleforabubblesortnottoswapfortwopasses. Apasswithoutswappingmeansthelistisalreadysorted. Share Follow answeredAug31,2009at17:20 BryanMenardBryanMenard 13k44goldbadges2929silverbadges4747bronzebadges Addacomment  |  0 Abubblesortisrarelyyourbestcasefordoingasort.Itisexceptionallyslowandinefficient.Manyothersortingalgorithmsarefaster.Forexample,youmayconsiderusingsomethinglikeaQuickSort. ThefastestsortingalgorithmIamawareofwasdevelopedbySteffanNilssonandisdescribedinthefollowingarticle. http://www.ddj.com/architect/184404062;jsessionid=VWL2QD1NWIEIJQE1GHOSKHWATMY32JVN?_requestid=396640 Ifyoujustwanttoknowhowtoimplementabubblesort,youcanfindagoodarticlehere. http://en.wikipedia.org/wiki/Bubble_sort Share Follow answeredAug31,2009at17:22 AnthonyGatlinAnthonyGatlin 4,36755goldbadges3535silverbadges5151bronzebadges 1 1 Youmaywanttonotethattheveryfastestsortsareveryoftenapplication-specific,thoughalmostallapplicationsareinsensitivetothatbenefitnexttotheexpenseofoptimizingbeyondawell-writtengeneralpurpose(library)algorithm. – SamHarwell Aug31,2009at17:30 Addacomment  |  0 eitherwikipediaori'mwrongbutformebestcaseandworstcasearebothO(n2)thisis fromthebookIntroductiontoAlgorithms BUBBLESORT(A) 1fori=1toA.length-1 2forj=A.lengthdowntoi+1 3ifA[j]