Bubble Sort Algorithm - GeeksforGeeks

Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in the wrong order. This algorithm is not ... Skiptocontent CoursesForWorkingProfessionalsLIVEDSALiveClassesSystemDesignJavaBackendDevelopmentFullStackLIVEExploreMoreSelf-PacedDSA-SelfPacedSDETheoryAllDevelopmentCoursesExploreMoreForStudentsLIVECompetitiveProgrammingGATELiveCourse2023DataScienceExploreMoreSelf-PacedDSA-SelfPacedCIPJAVA/Python/C++ExploreMoreSchoolCoursesSchoolGuidePythonProgrammingLearnToMakeAppsExploremoreAllCoursesTutorialsAlgorithmsAnalysisofAlgorithmsAsymptoticAnalysisWorst,AverageandBestCasesAsymptoticNotationsLittleoandlittleomeganotationsLowerandUpperBoundTheoryAnalysisofLoopsSolvingRecurrencesAmortizedAnalysisWhatdoes'SpaceComplexity'mean?Pseudo-polynomialAlgorithmsPolynomialTimeApproximationSchemeATimeComplexityQuestionSearchingAlgorithmsSortingAlgorithmsGraphAlgorithmsPatternSearchingGeometricAlgorithmsMathematicalBitwiseAlgorithmsRandomizedAlgorithmsGreedyAlgorithmsDynamicProgrammingDivideandConquerBacktrackingBranchandBoundAllAlgorithmsDataStructuresArraysLinkedListStackQueueBinaryTreeBinarySearchTreeHeapHashingGraphAdvancedDataStructureMatrixStringsAllDataStructuresInterviewCornerCompanyPreparationTopTopicsPracticeCompanyQuestionsInterviewExperiencesExperiencedInterviewsInternshipInterviewsCompetititveProgrammingDesignPatternsSystemDesignTutorialMultipleChoiceQuizzesLanguagesCC++JavaPythonC#JavaScriptjQuerySQLPHPScalaPerlGoLanguageHTMLCSSKotlinML&DataScienceMachineLearningDataScienceCSSubjectsMathematicsOperatingSystemDBMSComputerNetworksComputerOrganizationandArchitectureTheoryofComputationCompilerDesignDigitalLogicSoftwareEngineeringGATEGATEComputerScienceNotesLastMinuteNotesGATECSSolvedPapersGATECSOriginalPapersandOfficialKeysGATE2021DatesGATECS2021SyllabusImportantTopicsforGATECSWebTechnologiesHTMLCSSJavaScriptAngularJSReactJSNodeJSBootstrapjQueryPHPSoftwareDesignsSoftwareDesignPatternsSystemDesignTutorialSchoolLearningSchoolProgrammingMathematicsNumberSystemAlgebraTrigonometryStatisticsProbabilityGeometryMensurationCalculusMathsNotes(Class8-12)Class8NotesClass9NotesClass10NotesClass11NotesClass12NotesNCERTSolutionsClass8MathsSolutionClass9MathsSolutionClass10MathsSolutionClass11MathsSolutionClass12MathsSolutionRDSharmaSolutionsClass8MathsSolutionClass9MathsSolutionClass10MathsSolutionClass11MathsSolutionClass12MathsSolutionPhysicsNotes(Class8-11)Class8NotesClass9NotesClass10NotesClass11NotesChemistryNotesClass8NotesClass9NotesClass10NotesCSExams/PSUsISROISROCSOriginalPapersandOfficialKeysISROCSSolvedPapersISROCSSyllabusforScientist/EngineerExamUGCNETUGCNETCSNotesPaperIIUGCNETCSNotesPaperIIIUGCNETCSSolvedPapersStudentCampusAmbassadorProgramSchoolAmbassadorProgramProjectGeekoftheMonthCampusGeekoftheMonthPlacementCourseCompetititveProgrammingTestimonialsStudentChapterGeekontheTopInternshipCareersJobsApplyforJobsPostaJobHirewithUsKnowaboutJobathonJobathonPracticeAllDSAProblemsProblemoftheDayInterviewSeries:WeeklyContestsBi-WizardCoding:SchoolContestsContestsandEventsPracticeSDESheetCuratedDSAListsTop50ArrayProblemsTop50StringProblemsTop50TreeProblemsTop50GraphProblemsTop50DPProblems Comewritearticlesforusandgetfeatured Learnandcodewiththebestindustryexperts Getaccesstoad-freecontent,doubtassistanceandmore! Comeandfindyourdreamjobwithus GeeksDigest Quizzes GeeksCampus GblogArticles IDE CampusMantri Home SavedVideos Courses GBlog Puzzles What'sNew? ChangeLanguage ArrayMatrixStringsHashingLinkedListStackQueueBinaryTreeBinarySearchTreeHeapGraphSearchingSortingDivide&ConquerMathematicalGeometricBitwiseGreedyBacktrackingBranchandBoundDynamicProgrammingPatternSearchingRandomized RelatedArticles ▲ RelatedArticles SortingAlgorithmsSelectionSortAlgorithmBubbleSortAlgorithmInsertionSortMergeSortQuickSortHeapSortIterativeHeapSortCountingSortRadixSortBucketSortSomeinterestingcodingproblemsonSortingSortelementsbyfrequency|Set2FindtheMinimumlengthUnsortedSubarray,sortingwhichmakesthecompletearraysortedSortnumbersstoredondifferentmachinesSortalinkedlistof0s,1sand2sAPancakeSortingProblemSortnnumbersinrangefrom0ton^2–1inlineartimeSortanarrayaccordingtotheorderdefinedbyanotherarrayCheckifanytwointervalsintersectsamongagivensetofintervalsFindthepointwheremaximumintervalsoverlapSortanalmostsortedarraywhereonlytwoelementsareswappedFindapermutationthatcausesworstcaseofMergeSortSortingVectorofPairsinC++|Set1(Sortbyfirstandsecond)Sorting2DVectorinC++|Set2(Indescendingorderbyrowandcolumn)K-thsmallestelementafterremovingsomeintegersfromnaturalnumbersSortingBigIntegersLibraryimplementationofsortingalgorithmsKnowYourSortingAlgorithm|Set1(SortingWeaponsusedbyProgrammingLanguages)Comparatorfunctionofqsort()inCKnowYourSortingAlgorithm|Set2(Introsort-C++’sSortingWeapon)std::sort()inC++STLCqsort()vsC++sort()Arrays.sort()inJavawithexamplesCollections.sort()inJavawithExamplesSomeimportanttopicsaboutsortingHoare’svsLomutopartitionschemeinQuickSortSerialSortv/sParallelSortinJavaAnInsertionSorttimecomplexityquestionLowerboundforcomparisonbasedsortingalgorithmsWhichsortingalgorithmmakesminimumnumberofmemorywrites?WhendoestheworstcaseofQuicksortoccur?CanQuickSortbeimplementedinO(nLogn)worstcasetimecomplexity?WhyQuickSortpreferredforArraysandMergeSortforLinkedLists?WhereisHeapSortusedpractically?FindmemoryconflictsamongmultiplethreadsSortingTerminologyStabilityinsortingalgorithmsTimeComplexitiesofallSortingAlgorithmsExternalSorting SortingAlgorithmsSelectionSortAlgorithmBubbleSortAlgorithmInsertionSortMergeSortQuickSortHeapSortIterativeHeapSortCountingSortRadixSortBucketSortSomeinterestingcodingproblemsonSortingSortelementsbyfrequency|Set2FindtheMinimumlengthUnsortedSubarray,sortingwhichmakesthecompletearraysortedSortnumbersstoredondifferentmachinesSortalinkedlistof0s,1sand2sAPancakeSortingProblemSortnnumbersinrangefrom0ton^2–1inlineartimeSortanarrayaccordingtotheorderdefinedbyanotherarrayCheckifanytwointervalsintersectsamongagivensetofintervalsFindthepointwheremaximumintervalsoverlapSortanalmostsortedarraywhereonlytwoelementsareswappedFindapermutationthatcausesworstcaseofMergeSortSortingVectorofPairsinC++|Set1(Sortbyfirstandsecond)Sorting2DVectorinC++|Set2(Indescendingorderbyrowandcolumn)K-thsmallestelementafterremovingsomeintegersfromnaturalnumbersSortingBigIntegersLibraryimplementationofsortingalgorithmsKnowYourSortingAlgorithm|Set1(SortingWeaponsusedbyProgrammingLanguages)Comparatorfunctionofqsort()inCKnowYourSortingAlgorithm|Set2(Introsort-C++’sSortingWeapon)std::sort()inC++STLCqsort()vsC++sort()Arrays.sort()inJavawithexamplesCollections.sort()inJavawithExamplesSomeimportanttopicsaboutsortingHoare’svsLomutopartitionschemeinQuickSortSerialSortv/sParallelSortinJavaAnInsertionSorttimecomplexityquestionLowerboundforcomparisonbasedsortingalgorithmsWhichsortingalgorithmmakesminimumnumberofmemorywrites?WhendoestheworstcaseofQuicksortoccur?CanQuickSortbeimplementedinO(nLogn)worstcasetimecomplexity?WhyQuickSortpreferredforArraysandMergeSortforLinkedLists?WhereisHeapSortusedpractically?FindmemoryconflictsamongmultiplethreadsSortingTerminologyStabilityinsortingalgorithmsTimeComplexitiesofallSortingAlgorithmsExternalSorting BubbleSortAlgorithm ViewDiscussion ImproveArticle SaveArticle LikeArticle DifficultyLevel: Easy LastUpdated: 14Jul,2022 BubbleSortisthesimplestsortingalgorithmthatworksbyrepeatedlyswappingtheadjacentelementsiftheyareinthewrongorder.Thisalgorithmisnotsuitableforlargedatasetsasitsaverageandworst-casetimecomplexityisquitehigh. HowBubbleSortWorks? Consideranarrayarr[]={5,1,4,2,8} /videojs/videoapp.min.js?ver=0.1"> ClickherefortheCompleteCourse! FirstPass:  Bubblesortstartswithveryfirsttwoelements,comparingthemtocheckwhichoneisgreater. (51428)–>(15428),Here,algorithmcomparesthefirsttwoelements,andswapssince5>1.  (15428)–> (14528),Swapsince5>4  (14528)–> (14258),Swapsince5>2  (14258)–>(14258),Now,sincetheseelementsarealreadyinorder(8>5),algorithmdoesnotswapthem. SecondPass:  Now,duringseconditerationitshouldlooklikethis: (14258)–>(14258)  (14258)–>(12458),Swapsince4>2  (12458)–>(12458)  (12458)–> (12458)  ThirdPass:  Now,thearrayisalreadysorted,butouralgorithmdoesnotknowifitiscompleted. Thealgorithmneedsonewholepasswithoutanyswaptoknowitissorted. (12458)–>(12458)  (12458)–>(12458)  (12458)–>(12458)  (12458)–>(12458)  Illustration:     RecommendedPractice PunishtheStudents TryIt! FollowingaretheimplementationsofBubbleSort.  C++ //C++programforimplementation  //ofBubblesort #include usingnamespacestd;    //Afunctiontoimplementbubblesort voidbubbleSort(intarr[],intn) {     inti,j;     for(i=0;iarr[j+1])                 swap(arr[j],arr[j+1]); }    //Functiontoprintanarray  voidprintArray(intarr[],intsize) {     inti;     for(i=0;i    voidswap(int*xp,int*yp) {     inttemp=*xp;     *xp=*yp;     *yp=temp; }    //Afunctiontoimplementbubblesort voidbubbleSort(intarr[],intn) {     inti,j;     for(i=0;iarr[j+1])                 swap(&arr[j],&arr[j+1]); }    /*Functiontoprintanarray*/ voidprintArray(intarr[],intsize) {     inti;     for(i=0;iarr[j+1]){                     //swaparr[j+1]andarr[j]                     inttemp=arr[j];                     arr[j]=arr[j+1];                     arr[j+1]=temp;                 }     }        /*Printsthearray*/     voidprintArray(intarr[])     {         intn=arr.length;         for(inti=0;iarr[j+1]:                 arr[j],arr[j+1]=arr[j+1],arr[j]       #Drivercodetotestabove arr=[64,34,25,12,22,11,90]    bubbleSort(arr)    print("Sortedarrayis:") foriinrange(len(arr)):     print("%d"%arr[i],end="") C# //C#programforimplementation //ofBubbleSort usingSystem;    classGFG{     staticvoidbubbleSort(int[]arr)     {         intn=arr.Length;         for(inti=0;iarr[j+1]){                     //swaptempandarr[i]                     inttemp=arr[j];                     arr[j]=arr[j+1];                     arr[j+1]=temp;                 }     }        /*Printsthearray*/     staticvoidprintArray(int[]arr)     {         intn=arr.Length;         for(inti=0;i$arr[$j+1])             {                 $t=$arr[$j];                 $arr[$j]=$arr[$j+1];                 $arr[$j+1]=$t;             }         }     } }    //Drivercodetotestabove $arr=array(64,34,25,12,22,11,90);    $len=sizeof($arr); bubbleSort($arr);    echo"Sortedarray:\n";    for($i=0;$i Javascript Output Sortedarray: 12458 OptimizedImplementationofBubbleSort:  TheabovefunctionalwaysrunsO(n^2)timeevenifthearrayissorted. Itcanbeoptimizedbystoppingthealgorithmiftheinnerloopdidn’tcauseanyswap.  Belowistheimplementationfortheaboveapproach:  C++ //OptimizedimplementationofBubblesort #include usingnamespacestd;    //AnoptimizedversionofBubbleSort voidbubbleSort(intarr[],intn) {    inti,j;    boolswapped;    for(i=0;iarr[j+1])         {            swap(arr[j],arr[j+1]);            swapped=true;         }      }         //IFnotwoelementswereswapped       //byinnerloop,thenbreak      if(swapped==false)         break;    } }    //Functiontoprintanarray  voidprintArray(intarr[],intsize) {     inti;     for(i=0;i #include    voidswap(int*xp,int*yp) {     inttemp=*xp;     *xp=*yp;     *yp=temp; }    //AnoptimizedversionofBubbleSort voidbubbleSort(intarr[],intn) {    inti,j;    boolswapped;    for(i=0;iarr[j+1])         {            swap(&arr[j],&arr[j+1]);            swapped=true;         }      }         //IFnotwoelementswereswappedbyinnerloop,thenbreak      if(swapped==false)         break;    } }    /*Functiontoprintanarray*/ voidprintArray(intarr[],intsize) {     inti;     for(i=0;iarr[j+1])                  {                     //swaparr[j]andarr[j+1]                     temp=arr[j];                     arr[j]=arr[j+1];                     arr[j+1]=temp;                     swapped=true;                 }             }                //IFnotwoelementswere              //swappedbyinnerloop,thenbreak             if(swapped==false)                 break;         }     }        //Functiontoprintanarray      staticvoidprintArray(intarr[],intsize)     {         inti;         for(i=0;iarr[j+1]:                 arr[j],arr[j+1]=arr[j+1],arr[j]                 swapped=True            #IFnotwoelementswereswapped         #byinnerloop,thenbreak         ifswapped==False:             break             #Drivercodetotestabove arr=[64,34,25,12,22,11,90]     bubbleSort(arr)     print("Sortedarray:") foriinrange(len(arr)):     print("%d"%arr[i],end="")    #ThiscodeiscontributedbyShreyanshiArun C# //OptimizedC#implementation //ofBubblesort usingSystem;    classGFG {      //AnoptimizedversionofBubbleSort     staticvoidbubbleSort(int[]arr,intn)     {         inti,j,temp;         boolswapped;         for(i=0;iarr[j+1])                  {                     //swaparr[j]andarr[j+1]                     temp=arr[j];                     arr[j]=arr[j+1];                     arr[j+1]=temp;                     swapped=true;                 }             }                //IFnotwoelementswere              //swappedbyinnerloop,thenbreak             if(swapped==false)                 break;         }     }        //Functiontoprintanarray      staticvoidprintArray(int[]arr,intsize)     {         inti;         for(i=0;i$arr[$j+1])             {                 $t=$arr[$j];                 $arr[$j]=$arr[$j+1];                 $arr[$j+1]=$t;                 $swapped=True;             }         }            //IFnotwoelementswereswapped         //byinnerloop,thenbreak         if($swapped==False)             break;     } }            //Drivercodetotestabove $arr=array(64,34,25,12,22,11,90);  $len=sizeof($arr); bubbleSort($arr);    echo"Sortedarray:\n";    for($i=0;$i Javascript Output Sortedarray: 12345789 TimeComplexity:O(N2)AuxiliarySpace:O(1) WorstCaseAnalysisforBubbleSort: Theworst-caseconditionforbubblesortoccurswhenelementsofthearrayarearrangedindecreasingorder.Intheworstcase,thetotalnumberofiterationsorpassesrequiredtosortagivenarrayis(n-1).where‘n’isanumberofelementspresentinthearray.  Atpass1: Numberofcomparisons=(n-1)           Numberofswaps=(n-1)  Atpass2: Numberofcomparisons=(n-2)           Numberofswaps=(n-2)  Atpass3: Numberofcomparisons=(n-3)          Numberofswaps=(n-3)               .               .               . Atpassn-1: Numberofcomparisons=1            Numberofswaps=1 Now,calculatingtotalnumberofcomparisonrequiredtosortthearray=(n-1)+(n-2)+ (n-3)+...2+1=(n-1)*(n-1+1)/2 {byusingsumofNnaturalNumberformula}=n(n-1)/2    FortheWorstcase: Totalnumberofswaps=TotalnumberofcomparisonTotalnumberofcomparison(Worstcase)=n(n-1)/2Totalnumberofswaps(Worstcase)=n(n-1)/2 WorstandAverageCaseTimeComplexity:O(N2).Theworstcaseoccurswhenanarrayisreversesorted.BestCaseTimeComplexity:O(N).Thebestcaseoccurswhenanarrayisalreadysorted.AuxiliarySpace:O(1) RecursiveImplementationOfBubbleSort: Theideaistoplacethelargestelementattheirpositionandkeepdoingthesameforeveryotherelements. Approach: Placethelargestelementattheirposition,thisoperationmakessurethatfirstlargestelementwillbeplacedattheendofarray. Recursivelycallforrestn–1elementswithsameoperationandplacingthenextgreaterelementattheirposition. Baseconditionforthisrecursioncallwouldbe,whennumberofelementsinthearraybecomes0or1then,simplyreturn(astheyarealreadysorted). Belowistheimplementationoftheaboveapproach: C++ //C++codeforrecursivebubblesortalgorithm #include usingnamespacestd; voidbubblesort(intarr[],intn) {     if(n==0||n==1)     {         return;     }     for(inti=0;iarr[i+1])         {             swap(arr[i],arr[i+1]);         }     }     bubblesort(arr,n-1); } intmain() {     intarr[5]={2,5,1,6,9};     bubblesort(arr,5);     for(inti=0;i<5;i++)     {         cout<