7.3 Bubble Sort Algorithm| Data Structures Tutorials

first are given then you are arranging the data in either ascending order or descending order you can see and if character data is given then sorting means to arrange that data alphabetically fine many sorting techniques are there bubble sort insertion selection quick merge for a Dix shell heapsort okay we'll discuss all the sorting techniques one by one in this video I am going to discuss with you what is bubble sort first of all we'll discuss the working principle of this bubble sort with an example how bubble sort works how the data is to be sorted using this technique then we'll write down the code and after that we will see what modification we can do we can make in that algorithm of bubble sort for improving that algorithm okay now first of all let us take one example suppose data is given 15 16 6 8 and 5 and the state is stored in an array suppose there a name is a so the index would be from 0 1 2 3 4 something like this ok number of elements are 1 2 3 4 5 so suppose n is equal to 5 number of elements are n and n is equal to 5 now what is the basic principle of bubble sort in this case the adjacent to adjacent elements are to be compared if those elements are in correct order then it's fine will move further and if those elements are not in correct order then we will swap these elements now what do you mean by this in correct order see it depends you are you are sorting the data in ascending order or descending order now here by default if I say sorting then here I mean we are going to arrange the data in ascending order fine so the question is the data is given when area is given having these elements and you are going to arrange this data in ascending order you are going to sort the data in ascending order using bubble sort okay now what are the simple four nine bubble sort we are going to start from first element and in bubble sort this first element is compared with the second element fine and if these are in these elements are in you know in correct order these are not in correct order then we are going to swap these elements then next to it adjacent elements are to be compared the next two adjacent element are to be compared and next two adjacent elements are to be compared fine until we reach to the last of the serie so now according to the bubble sort first of all these two elements are to be compared a of zero name of there is a of zero is compared with you one or you can say in bubble sorting a of name of suppose I raise this a a of I is compared with a of I plus one fine and if these two elements are in wrong order then they are to be swap and if the these elements are in correct order then no swapping would be done fine now see 15 and 16 are to be compared we are going to arrange the data in ascending order then no swapping would be done so after that after this comparison the array would be something like that 15 16 6 8 and 5 because no swapping is to be done fine because 15 is less than 16 so 15 and 16 are in correct position now next is a 1 and a 2 are to be compared fine now see these are in wrong order so we are going to do swapping so 6 would be at this place and 16 would be it would be at this place so after swapping the array would be 15 6 16 8 and 5 now makes sense these two elements are to be compared a of two and a of three now now in this case also swapping would be done because 16 is greater than 8 so 16 would be at this side so the array would be is 15 6 8 16 and 5 next comparison is this with this one now also swapping would be done now the array would be 15 6 8 5 and 16 okay now this is known as this complete is known as pass 1 and here you can see the largest element from this array has bubbled up to its right position to the end of the array after completion of pass 1 the one element that which is the largest element has bubbled up to its correct position okay that is why it is known as bubble sort okay so now one element is in its correct position fine and this this complete is known as pass 1 now we are not still done with the sorting because the array is now this and this is not a sorted array now after this again we are going to start from first element okay after pass 1 we are going to start pass to and now in passed to array is 15 6 8 5 and 16 fine say apply the logic of bubble sort to adjacent we are going to start from the zeroth element and two adjacent elements have to be compared if they are in you know correct position the no swapping would be done if these elements are in wrong position then swapping would be done now start from here only first of all compare 15 and 6 so swapping would be done yes 6 fifteen eight five and sixteen next these two elements would be compared swapping would be done yes six eight the side 15 5 and 16 next these two elements would be compared swapping would be done yes 6 8 5 15 and 16 next these elements is to be compared 6 8 5 swapping would be done no 15 and 16 now we are reached we have reached to the end of this array now this is pass - now after completion of pass to say see two elements are at its correct position this is the largest element and this is the second largest element now these two elements are at its correct position now remaining elements are these three elements now again we are going to repeat the same state where we are going to we are going to start from the here only from the 0th position and we are going to compare a decent elements because still we are not done with the sorting so now in past three in past three see now array is what 6 8 5 15 and 16 now again we are going to start from this to this from starting only starting element swapping would be done knows no swapping would be done so the array is 6 8 5 15 and 16 next these elements are to be compared swapping would be done yes 6 5 here SEC 8 this position 59 16th next these elements 6 5 swapping would be done no hate 15 and 16 next is this one and this one 6 5 8 no swapping would be done 5916 now we are raised to the end of the array now this is passed 3 now after passed 3 3 element Harr at its correct position largest second largest and third largest now remaining are two elements now next pass would be passed for and in pass for arrays six five eight fifteen and sixteen now again same steps would be repeated from the zeroth element swapping sorry the comparison would be done with the adjacent element here swapping would be done yes so after swapping array would be five six eight fifteen or sixteen next this with this five no swapping six eight fifteen and sixteen next with this one five six no swapping would be done eight fifteen and sixteen next with this one five six eight fifteen and sixteen now this is the now we have reached to the end of the array okay now this is what the sorted array after pass for these four elements four elements these four elements are its correct position and total elements are five then obviously you can say it's common sense if five elements are there then you need to solve only four elements then obviously the fifth element would automatically be at its correct position right so now we have sorted these four elements so this element the fifth element is automatically at its correct position so now this array is now sorted how many passes you require one two three and four to sort how many elements five elements okay so how to calculate how many number of passes required number of elements minus one if number of elements are six then how many passes would be required five number of elements are ten the number of paths number of passes would be nine okay we will modify this also it's not like that if number of elements are ten then those elements would be sorted in nine passes only okay that is not a rule we are going to see that case also okay this is the general case if n elements are there then in bubble sort these these steps would be repeated how many times n minus 1 times C now within this path how many comparisons are there 1 2 3 4 4 comparisons right within this purpose also we have 1 2 3 4 comparisons within this past 1 2 3 4 this past 1 2 3 4 so 2 loops would be there one loop is 4 passes 1 2 3 4 and 2nd loop is for these comparisons or you can say iterations fine with in the past how many comparisons are there so one outer loop is for pass passes and within the passes one inner loop would be there for these comparisons fine now how to write the code write down the outer loop for suppose we are taking one variable I is equal to outer Lopes for these number of passes and how many times this loop would be executed n minus 1 times right because number of elements are air-five number of passes are 4 that is n minus 1 so this loop would be executed for how many times n minus 1 times so if we are going to start I from 0 then I should be less than n minus 1 and I plus plus I hope you got the concept ok here here suppose is from 0 so here you can say this pass is for i is equal to 0 when I is equal equal to 1 then this pass when I is equal to 2 then this pass and when I is equal to 3 then this pass okay that is why I am taking I is equal to from 0 to less than n minus 1 here n is 5 5 - one that is four so I is less than four it means I is equal to till I is equal to or you can say is till three if you take I is equal to one then you can say I is less than equal to n minus one now within this within this loop one inner loop would be there that is for suppose J is equal to zero and this loop is for these comparisons so how many comparison within each pass one two three four four four four and four it means n minus one comparison so you can say J is less than n minus one same fine we are going to start from zero that is why I'm taking J is less than n minus one if you write here J is equal to one then you can say J is less than equal to n minus 1 and here you write J plus plus fine now the main logic is what now we are we are going to check if this element is greater than this element then you do what swapping fine see here this case you can say here no swapping is done but here this element is greater than the next element so that is why we have done what swapping so here what you will check if if name of this array is a a of J is greater than a OH J plus 1 then you do what swapping and swapping is you I guess you know the logic you just take a temp variable and do the swapping so we do what temp is equal to a of J and a of J is equal to AO J plus 1 and then a of J plus 1 is equal to M this is the simple logic of swapping fine this is for if this is for the this for loop and this is for outer for loop like this but now you can modify this logic how see here how many comparisons are there for comparisons but after pass one the largest element is at its correct position right so in in this pass do you really need to compare 15 with 16 I guess no why so because we know that the last element is the largest element so no need to compare this element because we know that this element is always less than this element and no swapping would be done so here no need to do this comparison right in this path also see now after pass to these two elements are its correct position the largest element and the second largest element so here we know this is the largest element this is the second largest element fine then do you really need to compare eight with 15 no because these elements are it's correct position these are the two largest element so we can say that obviously this element would not be greater than this element so no need to compare this and obviously then no need to do this comparison fine so in this pass only two comparisons are required in this pass only one two three comparisons are required and in this pass see after pass three three elements are in its correct position so you can say this array is sorted and this is unsorted now you just have to compare these elements because these are already sorted so in this case we only need this comparison we don't need this comparison we don't need this one and we don't need this one no need to compare this element with this one because we know this is the third lads third largest element and this element cannot be greater than this element so why we are comparing this element we are only increasing the computation time no need to do this comparison fine now how to modify this code see this number of comparison depends on this I value because when I when you zero then how many comparison n minus-1 comparison but when I value is 1 then only 1 2 3 3 comparisons it means one comparison less so when I value is 2 then how many comparisons only 1 2 comparisons so you can say when I when you is increasing number of comparisons are decreasing so this number of comparison depends on high value fine and for number of comparison which loop is there this inner loop is for number of comparisons so we can modify this inner loop we have to modify this inner loop now how to modify this loop this loop now this loop is not dependent on this I because we are just going to start J with the 0 and then we are going to increase the day value till less than n minus 1 so now you can do what here you can write n minus 1 minus I n minus 1 minus I if you do this case then that that unnecessary comparisons can be avoided so how this will work see let us take one case let us take a value is equal to 2 fine 2 is less than n minus 1 n minus 1 is what n is 5 5 minus 1 is 4 yes this condition is true 2 is less than 4 then we'll go to this loop J is equal to 0 now J is equal to 0 so J is less than n minus 1 minus I n is equal to 5 5 minus 1 4 4 minus I value is 2 4 minus 2 is 2 yes 0 is less than 2 yes then we will enter this loop now we'll compare what a of 0 greater than a of 1 now see I is equal to 2 a of zero greater than a of one no this condition is not true because 6 is less than 8 fine so we will not enter in this condition because this condition is not true so we will not enter here finally what what should be done J plus plus now J is 1 now here what is there 5 minus 1 minus 2 that is 5 minus 3 is 2 now 1 is less than 2 yes we will enter again this loop now we will check a off now J is what one there is 1 greater than a or J plus 1 is 2 now check a of 1 is this one and a of 2 is this one if this one 8 is greater than 5 yes then swapping would be done so we have done the swapping 5 & 8 now J value it been increased now J is equal to 2 but 2 is not less than 2 so now they will not enter into this loop this condition is not true and we will go out from this loop and I plus 4 plus now I is equal to 3 how many comparisons are there 1 & 2 only so in this case how many comparisons are required one end to only because 15 and 16 I have already told you this comparison not required this comparison in this comparison is also not required fine so this is how you can you can avoid the unnecessary comparison so only by writing here n minus 1 minus I this is why we write here n minus 1 minus I now one more modification you can do in this algorithm and that is known as optimized bubble sort now what is that modification see in this case how many passes after how many passes you got the sorted array after four passes you can say after n minus 1 passes but every time this is not true maybe sometimes 10 elements are there and only after executing 3 passes you got the sorted array fine but when you apply this logic then this this program would be executed for how many times n minus 1 you can say if n is equal to 10 then for nine times this is to be executed fine and if suppose this this all the elements all the elements has been sorted after the third pass only then remaining passes are wasted wastage of time now so what you can do is so to get this point let us take one more example see now we are going to take one more example see suppose this is the array 16 14 5 6 & 8 how many elements five elements okay now according to this case how many passes would be required this this numerical urn you can say this program would be executed for how many buses four passes n minus 1 n minus 1 fine now see when you apply the bubble sort then you see that you see that in pass 1 yes swapping is done we got the largest element here in past two we have just done three comparisons and two largest elements are there and in past three in past three see when you are comparing 5 8 6 no swapping is there when you are comparing 6 with it no swapping is there and already 14 and 16 are its correct position after past 2 so you just have to sort these 3 elements you compare 5 8 6 6 with 8 no need to compare with 14 and 16 so here no swapping is there so in this part only two comparisons are there because we are going to write down this condition okay and minus 1 minus I so in this pass no swapping is there and after this pass only we got this sorted array see 5 6 8 14 and 16 but according to this program pass 4 is going to be there although we know that in past 3 only we got not no swapping and we are we got the sorted array but when you apply this case then pass 4 would be executed 1 comparison would be there for this five and six but that is of no use because we know that after past three only we got the sorted array so we have to know we have to modify this program how to modify this program we have to check if you got any pass in which no swapping is there see in which no swapping is there then you can say that then you can break this loop you can break this loop and you can say that now array is sorted if see in this pass one swapping is there 14 and 15 yes this swapping was there so here we go to one swapping here also we got swapping but in this pass no swapping is there so we can say that now that is sorted no need to do any other passes so how to check that condition so you can take one flag variable fine now in starting these in this loop suppose after this loop we are going to set this flag variable is equal to 0 and now if swapping is done then you can set this variable as 1 so the swap the code for swapping is here only so if the control has entered here it means swapping has been done if swapping has been done then you can set this variable within this if if condition flag is equal to 1 after this if is to be closed flags equal to 1 fine if flag is equal to 1 then it means swapping has been done and you cannot stop this loop fine and if sometimes it happens that no swapping is done if no swapping is done then control will not enter here fine so the flag variable will not be set to one flag variable will remain 0 right so you can check you can check here see here after this if and after this for fine after this you can check if flag is equal to is equal to zero then you can say break and after that you will close the outer loop here on if flag is zero then break it means break means from this loop you will go out and you can here print that arrays sorted this is not the complete code I am just write down I am just writing the logic you are you obviously you have to declare one array a size of the array and the flag variable and something like this so this is the optimized bubble sort so now let us trace out this thing this program is the help of one example let us take one I value high value is equal to suppose to see when I value zero so I value is 0 for this pass for this pass I value is 1 for this pass I value is 2 because we are going to start I from 0 so let us take I values 2 now if this this this chord is correct if we have written the flag variable and we have checked the flag where you will at the right position then you find out that I well you would not be increased to 3 because according to because if we don't write this flag variable this will this flag variable this this code then how many passes would be there four passes would be there and I would be increased from 0 to 3 but if you write down this code and if this code is correct then I value would not be increased to 3 the outer loop would be executed for I values 0 1 & 2 only for I value 2 because after this pass only we got the sorted array fine now check when I value is 2 so 2 is this 2 is less than n minus 1 n is 5 5 minus 1 that is 4 so this condition is true now control will go to this so now see flag is equal to 0 1 variable is there flat and the value of that is zero fine now J value is equal to 0 J is equal to less than n minus 1 minus I so this is what 0 is less than n is equal to 5 minus 1 minus AI value is 2 so 5 minus 3 that is 2 this condition is true so control will go within this loop now check a of JJ value 0 a of J greater than a of one here here when I value is 2 fine a of 0 greater than a of 1 is 5 greater than 6 no this this condition is not true so the control will not go within this condition fine now if this condition is not true then again what will happen J plus plus now J is equal to 1 now 1 is less than 5 minus 1 minus 2 vs 1 is less than 5 minus 3 is 2 when it's less than 2 yes this condition is true so control will go within this loop now check if is equal to j j is now 1 1 greater than 2 now see a of 1 a of 2 is 6 greater than 8 no this condition is not true so control will not go within this within these conditions within this if statement now j plus plus if control will not go within this condition then the next condition is the next statement to be executed if j plus plus now j is equal to 2 now condition is 2 less than 5 minus 1 minus 2 2 less than 2 this condition is not true now fine so now control will not go within this for statement if the condition is not true fine now where control will go now control will go to here only because in after j plus plus s not true so control if you will not write this one the finally control will go here only i plus plus but now we have two more statements in this for look within this for loop within this outer for loop fine so now control will go here and now we'll check if fly is equal to is equal to 0 say flag variable is 0 it has not been updated wise because in this case the control have not gone within this condition so flag variable is flag variable or remain 0 only it has not been set to 1 so flag is is equal to is equal to 0 and guess this condition is true so now this is what break now brakeman means what the loop in which this statement has been written fine when after finding this statement the control will go out from that loop or you can say the control will exit from that loop fine so now this statement this break has been written where within this outer for loop after the closing of this inner for loop fine within this outer for loop now we find the break statement now control will go from out from this this for loop out from this outer for loop fine now control will never go to I plus plus so I value would not be increased to 3 that is why this pass will never get executed and now maybe here you can write printf the the array has been sorted something like this okay you can print that sorry see this this this case is best when you have a sorted array suppose you have an array something like this 2 3 4 6 10 11 15 18 now this is there and you are supposed to apply bubble sort to sort this array this array is already sorted how many elements are there 1 2 3 4 5 6 7 8 n is equal to 8 now if you don't apply this logic if you don't apply this flag variable then how many times how many passes would be there seven passes fine this program would be executed for seven passes again and again but no need to execute for seven passes because this hair is already sorted now in one pass only we can come to know that this array is already sorted because in one pass when you will start with pass one then two is compared with three no swapping then three even wood will be compared with four no swapping then four with six no swapping six with ten no swapping no swapping no swapping and no swapping and if in any part you find out that no swapping has been done then you can say that this array is already sorted fine so no need to do seven passes no need to execute this program for seven passes just in one pass only you can come to know that array is sorted but only if you apply this logic if you apply this flag variable then only you can come to know in one pass only that this array is already sorted so this is the best case so best cases then our pairing is already sorted so in this case the time complexity is what how to find out time complexity see how many four loops are there one eight two so to find out the fine with time complexity you just have to check out how many times how many calculations are there how many computations are there within this inner for loop so the best cases array is already sorted so in one pass only you can come to know that array is already sorted so this loop will be executed for one time only and this look would be executed for how many times for n minus 1 and minus 1 comparison would be there so the time complexity would be order of n in best case when you apply this logic but in worst case worst case means the array is given in descending order and you are supposed to arrange there in ascending order in that case the time complexity would be order of n square why so because outer loop would all would be executed for how many times n minus 1 times and inner loop would also be executed for how many times approximately n minus 1 times so n minus 1 into n minus 1 that this it would be a polynomial function and when polynomial the polynomial is there then we just take the highest order of n so highest order of n is n square so we just simply write order of n square in worst case time complexity would be order of n square so in next video I am going to discuss with you the insertion sort so I'll see in the next video till then bye bye take care

Channel: Jenny's Lectures CS IT

Views: 927,036

Keywords: bubble sort, bubble sort algorithm, sorting algorithms, bubble sort in c, insertion sort, time complexity of bubble sort, dsa notes, ds, data structures, algorithms, ugc net computer science preparation, coaching classes, gate, GATE computer science, youtube channels, engineering, cse, it, CS/IT, b.tech subjects, best computer science youtube channel, jennys lectures, jayanti khatri, heap sort, selection sort, quick sort, sorting techniques in ds, ugc net, NTA ugc net

Id: o4bAoo_gFBU

Length: 35min 36sec (2136 seconds)

Published: Sat Jun 08 2019