Bubble sort Algorithm - Javatpoint

Bubble sort works on the repeatedly swapping of adjacent elements until they are not in the intended order. It is called bubble sort because the movement of ... ⇧SCROLLTOTOP Home DataStructure C C++ C# Java SQL HTML CSS JavaScript Ajax Android Cloud DesignPattern Quiz Projects InterviewQ Comment Forum DSTutorial DSTutorial DSIntroduction DSAlgorithm AsymptoticAnalysis DSPointer DSStructure DSArray DSArray 2DArray DSLinkedList LinkedList TypesofLinkedList SinglyLinkedList DoublyLinkedList CircularLinkedList CircularDoublyList SkiplistinDS DSStack DSStack ArrayImplementation LinkedListImplementation DSQueue DSQueue TypesofQueues ArrayRepresentation LinkedListRepresentation CircularQueue Deque PriorityQueue DSTree DSTree BinaryTree BinarySearchTree AVLTree BTree B+Tree DSGraph DSGraph GraphImplementation BFSAlgorithm DFSAlgorithm SpanningTree DSSearching LinearSearch BinarySearch DSSorting BubbleSort BucketSort CombSort CountingSort HeapSort InsertionSort MergeSort QuickSort RadixSort SelectionSort ShellSort BitonicSort CocktailSort CycleSort TimSort Differences Linearvsnon-linear Arrayvslinkedlist Stackvsqueue LinearvsCircularQueue LinearSearchvsBinarySearch SinglyLinkedListvsDoublyLinkedList BinaryvsBinarySearchTree TreevsGraph BinarySearchtreevsAVLtree RedBlackTreevsAVLtree BtreevsB+tree QuickSortvsMergeSort BFSvsDFS StackvsHeap Bubblesortvs.Selectionsort StackvsArray FullBinaryTreevsCompleteBinaryTree BinaryTreevsBTree Primitivevsnon-primitivedatastructure Datatypesvsdatastructure Misc TrieDataStructure HeapDataStructure SplayTree FundamentaloftheDS HashTable PreorderTraversal TreeTraversal ImplementationofQueueusingStacks ImplementationofStackusingQueue BinomialHeap PostorderTraversal SparseMatrix DetectloopinaLinkedlist InorderTraversal ConvertInfixtoPostfixnotation Convertinfixtoprefixnotation ConversionofPrefixtoPostfixexpression ConversionofPostfixtoPrefixexpression RemovetheloopinaLinkedList Implementtwostacksinanarray Reverseastackusingrecursion Detectcycleinadirectedgraph OptimalBinarySearchTree PriorityQueueusingLinkedlist BalancedBinarySearchTree BoundaryTraversalofBinarytree DiagonalTraversalofBinaryTree VerticalTraversalofaBinarytree GraphAlgorithms TimeComplexityofSortingAlgorithms ApplicationsofStackinDataStructure DictionaryDataStructure StructuredDataandUnstructuredData ListDataStructure TypesofTreeinDataStructure Abstractdatatypeindatastructure Disjointsetdatastructure DynamicDataStructure HashFunctioninDataStructure CompleteBinaryTree ThreadedBinaryTree DiameterofBinaryTree HeightofBinaryTree InorderTreeTraversalwithoutStack EnumerationofBinaryTrees MaximumWidthofaBinaryTree TypesofGraphinDataStructure PrimitiveDataType Semi-StructuredData AdvanceDataStructures SortanArrayof0's,1's,and2's StockSpanProblem ImplementationofDequebyCircularArray RotateOperationinLinkedList Subarraywithgivensum Self-organizingList UnrolledLinkedList TypesofSparseMatrices ApplicationofLinkedList TopologicalSorting TernarySearchTree StockSpanProblem TreapDataStructure QuicksortonDoublyLinkedList Inversioncount ExpressiontreeinDS GarbageCollectioninDS MergeSortonDoublyLinkedList SortStackusingRecursion LIFOApproachindatastructure BigONotationinDS BinaryTreeTraversalinDS QueueOperationsinDS WhatisaNon-LinearDataStructure FIFOApproachindatastructure Whatareconnectedgraphsindatastructure WhichPythondatastructureisimmutable Whichdatastructureisusedbymap Whatisiterationindatastructure Whatarelinearsearchandbinarysearchindatastructure HashTablevsSTLMap Recaman'sSequence Maximumarearectanglecreatedbyselectingfoursidesfromanarray Maximumnumberofdistinctnodesinaroot-to-leafpath DSMCQ DataStructureMCQ AdvancedDSMCQ →next ←prev BubblesortAlgorithm Inthisarticle,wewilldiscusstheBubblesortAlgorithm.Theworkingprocedureofbubblesortissimplest.Thisarticlewillbeveryhelpfulandinterestingtostudentsastheymightfacebubblesortasaquestionintheirexaminations.So,itisimportanttodiscussthetopic. Bubblesortworksontherepeatedlyswappingofadjacentelementsuntiltheyarenotintheintendedorder.Itiscalledbubblesortbecausethemovementofarrayelementsisjustlikethemovementofairbubblesinthewater.Bubblesinwaterriseuptothesurface;similarly,thearrayelementsinbubblesortmovetotheendineachiteration. Althoughitissimpletouse,itisprimarilyusedasaneducationaltoolbecausetheperformanceofbubblesortispoorintherealworld.Itisnotsuitableforlargedatasets.Theaverageandworst-casecomplexityofBubblesortisO(n2),wherenisanumberofitems. Bubbleshortismajorlyusedwhere- complexitydoesnotmatter simpleandshortcodeispreferred Algorithm Inthealgorithmgivenbelow,supposearrisanarrayofnelements.Theassumedswapfunctioninthealgorithmwillswapthevaluesofgivenarrayelements. beginBubbleSort(arr) forallarrayelements ifarr[i]>arr[i+1] swap(arr[i],arr[i+1]) endif endfor returnarr endBubbleSort WorkingofBubblesortAlgorithm Now,let'sseetheworkingofBubblesortAlgorithm. Tounderstandtheworkingofbubblesortalgorithm,let'stakeanunsortedarray.Wearetakingashortandaccuratearray,asweknowthecomplexityofbubblesortisO(n2). Lettheelementsofarrayare- FirstPass Sortingwillstartfromtheinitialtwoelements.Letcomparethemtocheckwhichisgreater. Here,32isgreaterthan13(32>13),soitisalreadysorted.Now,compare32with26. Here,26issmallerthan36.So,swappingisrequired.Afterswappingnewarraywilllooklike- Now,compare32and35. Here,35isgreaterthan32.So,thereisnoswappingrequiredastheyarealreadysorted. Now,thecomparisonwillbeinbetween35and10. Here,10issmallerthan35thatarenotsorted.So,swappingisrequired.Now,wereachattheendofthearray.Afterfirstpass,thearraywillbe- Now,movetotheseconditeration. SecondPass Thesameprocesswillbefollowedforseconditeration. Here,10issmallerthan32.So,swappingisrequired.Afterswapping,thearraywillbe- Now,movetothethirditeration. ThirdPass Thesameprocesswillbefollowedforthirditeration. Here,10issmallerthan26.So,swappingisrequired.Afterswapping,thearraywillbe- Now,movetothefourthiteration. Fourthpass Similarly,afterthefourthiteration,thearraywillbe- Hence,thereisnoswappingrequired,sothearrayiscompletelysorted. Bubblesortcomplexity Now,let'sseethetimecomplexityofbubblesortinthebestcase,averagecase,andworstcase.Wewillalsoseethespacecomplexityofbubblesort. 1.TimeComplexity Case TimeComplexity BestCase O(n) AverageCase O(n2) WorstCase O(n2) BestCaseComplexity-Itoccurswhenthereisnosortingrequired,i.e.thearrayisalreadysorted.Thebest-casetimecomplexityofbubblesortisO(n). AverageCaseComplexity-Itoccurswhenthearrayelementsareinjumbledorderthatisnotproperlyascendingandnotproperlydescending.TheaveragecasetimecomplexityofbubblesortisO(n2). WorstCaseComplexity-Itoccurswhenthearrayelementsarerequiredtobesortedinreverseorder.Thatmeanssupposeyouhavetosortthearrayelementsinascendingorder,butitselementsareindescendingorder.Theworst-casetimecomplexityofbubblesortisO(n2). 2.SpaceComplexity SpaceComplexity O(1) Stable YES ThespacecomplexityofbubblesortisO(1).Itisbecause,inbubblesort,anextravariableisrequiredforswapping. ThespacecomplexityofoptimizedbubblesortisO(2).Itisbecausetwoextravariablesarerequiredinoptimizedbubblesort. Now,let'sdiscusstheoptimizedbubblesortalgorithm. OptimizedBubblesortAlgorithm Inthebubblesortalgorithm,comparisonsaremadeevenwhenthearrayisalreadysorted.Becauseofthat,theexecutiontimeincreases. Tosolveit,wecanuseanextravariableswapped.Itissettotrueifswappingrequires;otherwise,itissettofalse. Itwillbehelpful,assupposeafteraniteration,ifthereisnoswappingrequired,thevalueofvariableswappedwillbefalse.Itmeansthattheelementsarealreadysorted,andnofurtheriterationsarerequired. Thismethodwillreducetheexecutiontimeandalsooptimizesthebubblesort. Algorithmforoptimizedbubblesort bubbleSort(array) n=length(array) repeat swapped=false fori=1ton-1 ifarray[i-1]>array[i],then swap(array[i-1],array[i]) swapped=true endif endfor n=n-1 untilnotswapped endbubbleSort ImplementationofBubblesort Now,let'sseetheprogramsofBubblesortindifferentprogramminglanguages. Program:WriteaprogramtoimplementbubblesortinClanguage. #include voidprint(inta[],intn)//functiontoprintarrayelements { inti; for(i=0;i usingnamespacestd; voidprint(inta[],intn)//functiontoprintarrayelements { inti; for(i=0;i

Output Program:WriteaprogramtoimplementbubblesortinPHP. "; printArray($a); for($i=0;$i<5;$i++) { for($j=0;$j<5;$j++) { if($a[$i]Aftersortingarrayelementsare-
"; printArray($a); ?> Output Program:Writeaprogramtoimplementbubblesortinpython. a=[35,10,31,11,26] print("Beforesortingarrayelementsare-") foriina: print(i,end="") foriinrange(0,len(a)): forjinrange(i+1,len(a)): ifa[j]