Bubble Sort - Data Structures & Algorithms Tutorial Python #14

Key Takeaways

we will be discussing bubble short in this video as usual we'll have some theory then we will implement bubble shot in python and at the end i have an interesting exercise for you to work on so make sure you watch till the end why sorting is needed in first place when you're developing big projects such as let's say you are building a system for wireless store where in your computer you might have so many transactions let's say you have 30 000 transactions and i want to sort this transaction by the amount i want to know who bought the maximum amount of inventory from my store sometimes i might want to sort this based on a name so sorting is a very common use case when you are doing software development and bubble short is one of the sorting techniques the way it works is let's say you have a list of numbers and you want to sort this list you will begin by comparing the first two numbers 38 and 9 then if 38 is greater than 9 i will swap it so now 9 came in front of 38 then i repeat this process for second and third element so i compare 38 and 29 29 is less than 38 so of course i will swap that and now my list looks something like this again do the same process for element number three and element number four so i can keep on doing this process until the very end and what will happen as a result of this process is 38 which was the highest number will go towards the end that's why this is called bubble shot when you have a bubble in a water bubble will pop up it will come from the bottom to up similarly 38 which was the highest element popped up from the bottom it went all the way up to the correct position so if you look at all the numbers 38 should be in the last position because it is the highest number now we got 38 in its right position let's repeat the same process again and what happens you can literally take knot and pen and do this process by hand i think you should do it because that will be very helpful so now i compare 9 and 29 and that was at the correct position so i did not do anything but then i compared 9 29 and 7 and when i compare that i found 7 should be in front of 29 so i swept then i compare 29 and 2. then 15 and 29 so remember what we're doing in each iteration is we come take two consecutive elements and compare and if the first element is greater than the second then we just change the position we just swap them and when you do that after second iteration you got 29 in its correct position so now last two elements of my list are already sorted so if i keep on doing this process for as many time as there are elements in the list i will get my whole list sorted if you think about it i don't need to do it n times let's say n is the size of an array i need to do it only n minus one time i have to do this for loop for all the elements and then within that for loop every time i am comparing two consecutive elements and running the second for loop throughout the list so if you have two for loops running your big o complexity is order of n square if you don't know about baker complexity please watch my big o notation tutorial in the same playlist it was i think a second video you'll get an idea so time complexity here is order of n square and the space complexity is order of 1 because we are not using any additional space we are just using the same array and we are swapping the limit and for swapping the element we need some one extra uh variable let's implement this in python now in my python code i have this element list which i want to sort using bubble shot method right now method is empty and we are going to implement it as per the theory we saw in the presentation the first thing i want to do is i want to gather the element size because that will be very useful okay and what we did if you think about the presentation that we had is we go through all the elements one by one and we compare consecutive elements like this to first then these two then this two and so on so how can you do that well you can just say for i in range size minus 1 because you want to go all the way till here only because after you compare 88 and 34 there is no element after 34 hence i have minus 1 here and you want to compare two consecutive elements so let's compare them so the first element would be what i okay and you want to compare that with the second element so if i is greater than i plus i plus 1 okay then you want to swap them swatch swap meaning change their position so how do you do that standard ways you can take a temporary variable store elements there because i want to do this elements i is equal to elements i plus 1 and then elements i plus 1 is equal to so you're doing elements this okay so this will be tmp and when you are done running this loop you would have uh sorted the highest element so the highest element which is 88 will come at the highest position which is at the end so let's just run this this code is not complete i know but i want to run it to see what happens right click run in pycharm and you realize that 88 came at the right position you see now if i do this process two times then the second highest element will come at the right position which will which is 67 let's say so i want to keep 67 here so how do i do that well just think about it if you do for any loop like 4k in let's say range 2. you're doing this two times okay and when you do that you will see that 67 also came in the right position so how many times you want to repeat this process you want to repeat this process as many times as n minus 1 basically n is the size of the array and n minus 1 because when you repeat process two times you get two maximum numbers in the right position similarly i want to get all this number in the right position and the first number will automatically come into the right position okay so the outer loop so so let me just change this inner loop to call it j okay i'm just changing the loop variable nothing else because this is a standard convention we have so i'm just calling it j out outside loop i am calling it i and i want to run this loop for size minus one i hope it makes sense it's pretty simple actually when you run this code you will notice the whole list is sorted now uh this process is probably not the most efficient because uh this see we are we are having couple of uh inefficiencies okay so what is that when you ran this loop for two times unless the last two elements were in the right position third time when you run the loop you need to run it only till this point you can ignore the last two elements because they are already sorted and the way to ignore that would be here you can do minus i so minus i will be when you are in second iteration you don't go all the way till end you go all the way till n minus two elements okay that way you save some time basically on iteration right now code is running very fast but when you have bigger less a million elements it might save some time some millisecond also uh let's let's do this okay let me run this for already a sorted array so let's say this array is already sorted and when i run it of course it's going to remain sorted but what will happen is i set a breakpoint here right click debug okay and when i go to next point see it keeps on repeating this loop although the array is sorted is there a way to detect that array sorted yes there is a way think about it in your inner loop let's say if you go through the entire list and if you don't end up swapping any element it means your array sorted so here we can create a variable called swap which is false and whenever you are swapping you just say swap is equal to true and what we'll do it you will do is your inner loop after completing if it has not swept a an element the swept flag will be false okay so you can say if not swapped break now you can break the outer loop okay and this will make your algorithm more efficient we can verify it so if i debug here and if i go here see outer loop i am you know my first iteration okay inner loop see in my outer loop i just did one iteration and i'm i'm done now so the complexity of this will be order of n it is not order of n square because you went through the list only one time if you don't have this code let's say i don't have the score here okay without this code what what was happening you might have realized it you start with the outer loop the first iteration then you go through all the elements now see you're in a second iteration this is not needed then you go through all the element you go to third iteration so all of that was not needed and this can be made efficient by using this swap flag by the way you can use this sorting algorithm to sort the strings too for example i have this list of string and when i call bubble shot on top of it when i run it you see these are alphabetically sorted now a comes first then c then d and so on this is because in python you can use this greater than operator on strings you can quickly verify it if you say a is greater than b it returns false but if you say a is less than b it returns true similarly it does the comparison for the whole string as well for example you have abc and you have adx it will return true all right so that's all i had for uh bubble short and now comes the most interesting part of this tutorial which is an exercise you cannot learn things unless you practice on your own and you do this exercise so i have this interesting exercise for you where i have the transaction recourse of electronic store and i want you to modify my bubble sort function to take a key argument where i can specify a key inside my dictionary and using that key it should do shorting for example if i say my key is transaction amount then it has sorted all these records by transaction amount you can see 200 400 800 000 if i say key is equal to name it will sort them using the names the solution is actually simple you have to just take my function by the way i'm gonna provide my jupyter notebook in the video description below so make sure you check the video description it has a link of this exercise as well and you take my function add this key element and then when you are doing that comparison you know at that time you have to make some change after you have uh worked on solving on your own you can click on solution link here to verify your answer don't click on solution directly that's not good you should try on your own and then you should try to see the solution i hope you're liking this tutorial if you do please give it a thumbs up share it with your friends also share it with your friends on facebook linkedin whatever medium i will see you in next tutorial it's gonna be a different sorting technique thank you