Data Structure - Bubble Sort Algorithm - Tutorialspoint

Bubble sort is a simple sorting algorithm. This sorting algorithm is comparison-based algorithm in which each pair of adjacent elements is compared and the ... Home CodingGround Jobs Whiteboard Tools Business Teachwithus DataStructures&Algorithms DSA-Home DSA-Overview DSA-EnvironmentSetup Algorithm DSA-AlgorithmsBasics DSA-AsymptoticAnalysis DSA-GreedyAlgorithms DSA-DivideandConquer DSA-DynamicProgramming DataStructures DSA-DataStructureBasics DSA-ArrayDataStructure LinkedLists DSA-LinkedListBasics DSA-DoublyLinkedList DSA-CircularLinkedList Stack&Queue DSA-Stack DSA-ExpressionParsing DSA-Queue SearchingTechniques DSA-LinearSearch DSA-BinarySearch DSA-InterpolationSearch DSA-HashTable SortingTechniques DSA-SortingAlgorithms DSA-BubbleSort DSA-InsertionSort DSA-SelectionSort DSA-MergeSort DSA-ShellSort DSA-QuickSort GraphDataStructure DSA-GraphDataStructure DSA-DepthFirstTraversal DSA-BreadthFirstTraversal TreeDataStructure DSA-TreeDataStructure DSA-TreeTraversal DSA-BinarySearchTree DSA-AVLTree DSA-SpanningTree DSA-Heap Recursion DSA-RecursionBasics DSA-TowerofHanoi DSA-FibonacciSeries DSAUsefulResources DSA-QuestionsandAnswers DSA-QuickGuide DSA-UsefulResources DSA-Discussion SelectedReading UPSCIASExamsNotes Developer'sBestPractices QuestionsandAnswers EffectiveResumeWriting HRInterviewQuestions ComputerGlossary WhoisWho DataStructure-BubbleSortAlgorithm Advertisements PreviousPage NextPage  Bubblesortisasimplesortingalgorithm.Thissortingalgorithmiscomparison-basedalgorithminwhicheachpairofadjacentelementsiscomparedandtheelementsareswappediftheyarenotinorder.ThisalgorithmisnotsuitableforlargedatasetsasitsaverageandworstcasecomplexityareofΟ(n2)wherenisthenumberofitems. HowBubbleSortWorks? Wetakeanunsortedarrayforourexample.BubblesorttakesΟ(n2)timesowe'rekeepingitshortandprecise. Bubblesortstartswithveryfirsttwoelements,comparingthemtocheckwhichoneisgreater. Inthiscase,value33isgreaterthan14,soitisalreadyinsortedlocations.Next,wecompare33with27. Wefindthat27issmallerthan33andthesetwovaluesmustbeswapped. Thenewarrayshouldlooklikethis− Nextwecompare33and35.Wefindthatbothareinalreadysortedpositions. Thenwemovetothenexttwovalues,35and10. Weknowthenthat10issmaller35.Hencetheyarenotsorted. Weswapthesevalues.Wefindthatwehavereachedtheendofthearray.Afteroneiteration,thearrayshouldlooklikethis− Tobeprecise,wearenowshowinghowanarrayshouldlooklikeaftereachiteration.Aftertheseconditeration,itshouldlooklikethis− Noticethataftereachiteration,atleastonevaluemovesattheend. Andwhenthere'snoswaprequired,bubblesortslearnsthatanarrayiscompletelysorted. Nowweshouldlookintosomepracticalaspectsofbubblesort. Algorithm Weassumelistisanarrayofnelements.Wefurtherassumethatswapfunctionswapsthevaluesofthegivenarrayelements. beginBubbleSort(list) forallelementsoflist iflist[i]>list[i+1] swap(list[i],list[i+1]) endif endfor returnlist endBubbleSort Pseudocode WeobserveinalgorithmthatBubbleSortcompareseachpairofarrayelementunlessthewholearrayiscompletelysortedinanascendingorder.Thismaycauseafewcomplexityissueslikewhatifthearrayneedsnomoreswappingasalltheelementsarealreadyascending. Toease-outtheissue,weuseoneflagvariableswappedwhichwillhelpusseeifanyswaphashappenedornot.Ifnoswaphasoccurred,i.e.thearrayrequiresnomoreprocessingtobesorted,itwillcomeoutoftheloop. PseudocodeofBubbleSortalgorithmcanbewrittenasfollows− procedurebubbleSort(list:arrayofitems) loop=list.count; fori=0toloop-1do: swapped=false forj=0toloop-1do: /*comparetheadjacentelements*/ iflist[j]>list[j+1]then /*swapthem*/ swap(list[j],list[j+1]) swapped=true endif endfor /*ifnonumberwasswappedthatmeans arrayissortednow,breaktheloop.*/ if(notswapped)then break endif endfor endprocedurereturnlist Implementation Onemoreissuewedidnotaddressinouroriginalalgorithmanditsimprovisedpseudocode,isthat,aftereveryiterationthehighestvaluessettlesdownattheendofthearray.Hence,thenextiterationneednotincludealreadysortedelements.Forthispurpose,inourimplementation,werestricttheinnerlooptoavoidalreadysortedvalues. ToknowaboutbubblesortimplementationinCprogramminglanguage,pleaseclickhere. PreviousPage PrintPage NextPage  Advertisements