Python Sorting Algorithm Visualizer Tutorial

[Music] hello everybody and welcome to another youtube video so in today's video i am going to be showing you how to create a sorting algorithm visualizer in python using pygame now i have the demo in front of me so let me show you exactly what the finished product will look like and then i'll talk about some prerequisites and we'll get into the code alright so this is the program you can see right now we're going to be looking at the bubble sort algorithm in ascending order if i hit space we can actually view the visualization now there is ways to speed up this visualization right now i just have it on kind of a default setting so you can actually view what's going on but of course if i want to i can reset so this would just give me a new starting list here to actually sort i can change the algorithm that i want to view so in this case i'll go to insertion sort and now we can see that you know obviously something different is happening and then if i want to i can change from ascending order to descending order so once this is done i'll be able to do that right now i can't because uh what do you call we're in the middle of a sort anyways if i stop this by resetting and now i change this to sorry ascending order or descending order whatever it is you can see that we'll go in the opposite direction well that's kind of how this program works now i'm only going to show you how to implement insertion sort and bubble sort but the way i've written this code is that it's going to be very easy to plug in pretty much any other sorting algorithm that you want you will have to do some manual changes and figure a few things out but if you wanted to visualize say heap sort or some other type of algorithm you just have to write that sorting algorithm make it so it draws the different steps and well this program would work for you all right so with that said let's talk about a few prerequisites before going through all of this code in this long tutorial and then of course i'll show you how to build this so the first thing i'll state is that this tutorial is not designed for beginners i'm going to assume you have some familiarity with python and with programming in general i'm going to be showing things like object-oriented programming functions i'm actually going to show you a generator as well although i'll explain that when we get to that part but if you are not familiar with python and you want to follow along with this then you should check out programmingexpert.io from the link in the description now programming expert is the best platform to learn how to code if you had gone through that content you would have learned literally everything you need to know to follow along with this tutorial and hundreds of others that are for intermediate programmers on my channel anyways check it out from the link in the description you can use the code tim for a discount on the platform other than that we're going to be using pie game here pie game will be for the visuals you don't have to know pi game i will explain to you the few features that we use as we go through the code so that said let me head over to sublime text and we can actually start implementing this project all right so i'm in sublime text this is the code editor i'm going to use for this video you can use any editor that you would like and i have python version 3.9 installed as well as pygame now you can use any version of python above 3.6 now the first step here is going to be to install pygame if you don't already have it installed then you go to your command prompt or your terminal and simply type in pip install pi game if that doesn't work for you i will leave two videos on the screen that show you how to install pi game one for mac and one for windows once we have pi game installed though let's go into our python code file just notice i have mine called tutorial.pi and let's import pygame let's import the random module i'm going to use this to generate the starting list when we actually want to sort something right and then i'm just going to say pygame dot init all right so the first thing we can do here is we can set up our pi game window and a few kind of global constants that we want to have access to throughout the entirety of the program so what i could do here is to find maybe like 20 or 30 global variables stuff like different colors stuff like the window size width height all of that but that means that when i'm accessing these values in functions i'm going to be accessing a global value and i don't like using global variables because that means any of the functions that i write here i can't port them over to another program if they're using something from the global scope so instead what i'm going to do is set up a class i'm going to call this class game information or i guess not game information i guess it would be something like drawing information and i'm going to put all of the stuff in here in this class that i want to have as kind of global values to be accessed you'll see what i mean in a second but for now let's create a class i'm going to call this what do we want to call this draw and then information like that now the idea here is we'll instantiate this class at the beginning of our program and pass to its stuff like the width the height the starting list it will then store all of those values as well as any additional values that we need and then we can just pass this instance to all of the different functions that need it and it can access all of this information so the first thing i'm going to do here is just to find a bunch of colors so i'm going to say black is equal to 0 0 0 i'm going to say white is equal to 255 255 255. these are in rgb so red green blue obviously the maximum value is 255. we're also going to want green so i'm going to say green is equal to zero 255 and then zero we'll want red this is going to be equal to zero or sorry 255 zero and zero i want a gray this will be equal to 128 128 and 128 and then i want my background underscore color so let's do this if i could get the autocomplete background color to be equal to white okay so notice i'm defining all of these kind of global values as class attributes that just means they're defined directly in the class body as opposed to a constructor okay so those are all i need for right now i will define a few more in a second and by the way if you see me looking over here to kind of the right of my screen that's because i'm referencing the code that i already wrote obviously i don't have all of this memorized okay so now that we have all of our colors defined these are what we're going to use for our different rectangles and the bars and the text and all of that i want to define an initialization and this initialization here is going to take in a width a height and then a list which will be lst now this list is going to be the starting list that we actually want to sort and we're going to store that inside of this instance so i'm going to say self.width is equal to width i'm going to say self.height is equal to height and then i will actually set up a few other attributes in here that we're going to need so the first additional attribute i'm going to add here is going to be the window so whenever working with pi game we need to set up a screen or a window that we're going to draw everything on now we need to access that pretty much everywhere in the program so i'm going to put that as an attribute on the class so that it's very easy to access so i'm going to say self.window is equal to pygame dot display dot set underscore mode and then i'm going to pass as a tuple here the width and the height so whenever you create a window in pi game this is how you do it say pygame.display.set underscore mode pass the width and the height as a tuple and we will set the width and the height in a second when we actually initialize this instance okay then i want to set a caption for this window so i'm going to say pygame dot display dot set underscore caption not a capital but caption like that and then i can say sorting algorithm and then visualization or visualizer whatever you want to call it but this will be kind of the name of the window and then after that i'm going to call a new method that i'm going to define called set underscore list and pass this lst so now i'm going to go and make a method i'm going to say define this is going to be called set underscore list this is going to take in self if i could type properly as well as lst and what we're going to do here is set a bunch of attributes that we need related to the list so now i want to talk about how we're actually going to create kind of the visualization so you saw that i had a bunch of bars on the screen in fact let me just run the other program here because this will give us a good visualization okay so you can see i have a bunch of different bars here right now first of all i have these bars in three different colors just so that they're easy to see i kind of have a dark gray lighter gray and then the lightest gray right so i have three different colors now all of these bars have a specific width and a specific height however the width of these bars is going to depend on how many of them i have for example if i go to my other program here just bear with me for one second and i change the number of values that i have to say 25 as opposed to 100 because previously i had 100 notice how we're going to have bars that are a little bit wider right so we need our bars to adjust based on the number of values in our list and then same thing with the height of our bars the height of our bars is going to be determined by the range of values in our list so if we have a range of say 1 to 100 then each one pixel or each value one is going to be represented by four or five pixels right whereas if we have a range of one to a thousand then maybe the value one is only represented by 0.5 pixels hopefully that kind of makes sense but the idea is we want this to be dynamic so we need to kind of calculate the width of all of these bars and what the height of one individual kind of unit one number will be based on the range of values we have within our bars okay hopefully that makes a little bit of sense but that's what i'm going to attempt to do now so the first thing i'm going to do in here is just say self.lst is equal to lst because i just want to store this list internally i'm going to say self. and this is going to be max underscore value is equal to the maximum of the list this is going to give me the maximum number in there and i'll say self.min underscore value is equal to the min in the list and just because i think it makes sense to do this we're going to put the min before the max okay great so now that we have this the first thing i want to do is calculate the width of every one of our bars now the width of these bars will be determined by how many of them we have and the width of our screen and in fact if i run this one more time you'll see here that we actually have kind of a padding on the left and the right hand side so we want to include that in the calculation as well if we want to have say 100 pixels from the left or right hand side so that the bars are kind of in the center and they don't look like they're kind of touching the edge of the screen hopefully you see what i mean but essentially we have a little bit of padding and that's kind of what i'm talking about you can see the padding is maintained when i reset this so let's now implement one more variable here i'm going to call this the i've got to go look at my cheat sheet to make sure i'll mess this up i'm going to call this the side pad and the side pad is going to be equal to 100 pixels now what this is going to tell me is i want 100 pixels in total as the padding from the left and the right hand side so 50 pixels on the left and fix 50 pixels on the right okay so what i'm going to do here is say self dot and then this is going to be pixel underscore width and really this should be like block width or something but for now i'll just go with pixel width kind of a weird name but that's what i did in my other sheet so just so i don't mess myself up we'll go with that and what i'm going to do is i'm going to take the self.width and i am going to divide that or sorry first of all i'm going to subtract that from my self dot side pad okay so let's go self.sidepad and then i'm going to divide that by the length of my list so i need to put parentheses here but let's talk about why we're doing this so we have the width of our screen which is say 500 pixels or something like that and then we have a side padding and in this case i've made it 100. now this is the total amount of padding including the left and the right hand side so i want to determine how wide my pixels should be based on how much area i'm going to have to put them in and the length of the number of kind of blocks that i'm going to need and in fact you know what let's just call this block width because pixel width is really throwing me off that's a very poor name okay so we have block width so i'm taking the self.width dividing it by the self.sidepad and that's going to tell me the total area i actually have to represent each of my blocks in so then i'm going to take whatever my total kind of drawable area is and divided by the length of my list which is the number of blocks that i have now i'm just going to round this value because we can't draw like fractional amounts so i just want to round that to whatever the nearest decimal is okay that's great for the block width now for the block height this is going to represent the height of one kind of unit of a block this is really weird to explain but let's say we have the number 100 essentially i want to multiply this by the block height to determine how high a hundred should be right how large should that be on the screen and this is going to depend on the largest number in my list and the smallest number on my list because again if say the largest number is 10 000 then 100 is going to be quite small but if the largest number is 100 then this is going to be the maximum possible height hopefully that makes sense but that's what this next calculation is going to do which is a little bit complicated so i'm going to say the self.height then this is going to be minus the self.top underscore pad and the top pad is going to be the padding that we're going to have to allow us to draw like the controls and some of the text at the top of the screen so i'm going to implement my top pad now i'm going to say top pad is equal to and for now we'll go with 150 pixels we can always modify this later on okay so we're going to have the self.height minus the self.top pad this is going to tell us again the total drawable area that we have and then what we're going to do is divide this by the self.max value minus the self.min value and we're going to round all of this so let's round all of this in parentheses so the reason i'm doing this is the maximum value minus the minimum value is going to tell me the number of values in my range so if the minimum value is 1 and the maximum value is 100 then the range of numbers i have is 99 right i have 99 distinct numbers whereas if we have something like a thousand and maybe negative 10 thousand i'm going to have a lot much larger range and so the height of kind of one unit is going to be a lot smaller again hopefully that makes sense but that's kind of what this calculation is doing okay now the last thing i'm going to do is say that the self.start underscore x so this is where i'm going to start drawing my blocks for the x coordinate is going to be equal to and then this will be the self dot side pad integer divided by 2 just to make sure i get a whole number now just to quickly explain the coordinate system system of pi game in case you're unfamiliar let me load this screen back up the top left hand corner of the screen is zero zero so as you go down the y increases and as you go to the right the x increases so when i say something like start at self dot side pad over two that's telling me to start kind of right here where this block is starting right hopefully that makes sense okay so there we go we are almost finished the draw information class there's a few other things we need to add but for now i think this is fine and i'm just double checking to make sure we didn't mess anything up looks good so far okay so now that we have this class the next thing i want to do is write a function that's going to generate the starting list for us because we need a starting list to actually sort and we'll be able to determine you know how many elements we want in the list and what the range of the elements is so i'm going to create a function i'm going to call this generate starting underscore list okay and this will take in n and then min and max and i'll just make these val so they don't shadow the min and max function okay so n will be the number of elements that we want in our starting list min will be the minimum possible value and max will be the maximum possible value and we'll just randomly generate a list here so i'm just going to say lst is equal to that and i'll say 4 underscore in range n so just do this n times essentially then i'm going to generate a random value so i'm going to say value is equal to random.randint and i'm going to put this between the min value and the max value and this will give me a number within this range inclusively meaning it will include both the minimum and maximum value as possible values to generate okay then i'm going to say lst dot append value like that and if i wanted to i could shuffle this list but this will already give me a random list of values so what i can do here is just return lst great now we have our starting list generate now that we've done that i actually want to put something on the screen i want to see my window so i'm going to implement a function which is going to be kind of our main driver code which i'll call me so i'm going to say define main and then inside of here what we're going to do is we're actually going to render the screen we're going to set up our main event loop which is going to allow us to press buttons click the x button all of that kind of stuff and then we'll start drawing our list onto the screen that will be the next step so for now what i'm going to do is say that run is equal to true this is just going to be a variable for my while loop i'm going to say i'll run like that and inside of here i'm going to set up my pi game event loop so whenever you implement something in pi game you need a loop constantly running in the background because if you don't have that then you'll just say draw something on the screen and the program will immediately end so i need a loop that's going to be handling all of the events that are occurring like me attempting to start sorting right or changing from descending order to ascending order or trying to exit the program whatever we need a loop to handle that so this is going to be my loop right here and one thing that we can do inside of our loop is we can put something called a clock which will regulate how quickly this loop can run so i'm going to say clock is equal to pi game dot time dot and then with a capital c like that clock so i'll explain the clock in a second but let's go clock.tick i'm going to put 60 60 would be our fps so this is the maximum number of times that this loop can run per second right now i'm going to make it 60. you could of course increase this to whatever you want but we'll just go with a hard code of 60 for right now and now i'm going to do my kind of handling of events so i'm going to say for event in and then pygame.event.get this is going to return to us a list of all of the events that have occurred since the last loop so since last time this was called it'll give it give it to us in the event variable and then we can check the event variable for specific events so i can do something like if event is equal to pygame.quit with all capitals make sure it's all capitals then i can say run is equal to false and then at the end of this while loop here i can say pi game dot quit so as soon as we break out of this while loop we will then end the pi game program perfect now one thing i want to do in here though is i want to actually draw the window and show that on the screen so all i'm going to do is say pygame dot display dot update and when you do this it will update the display now right now we haven't drawn anything onto this display so we're not going to see that when i call update it will just render the display so we'll actually see it and then we can continue from there okay uh last thing i want to do here is just say if underscore the score name underscore underscore equals underscoring score main underscore underscore then i want to call the main function now this is just going to make sure that we actually are running this module by clicking the run button or running this module directly before we call the main function if we were to import this module this line would not run but if we actually run this module directly then we run the main function okay and just to go over something that i don't think i mentioned this right here so if event equals pi game dot quit essentially that is hitting the red x in the top right hand corner so you need to manually handle that if you click the x and you don't have this it's not going to do anything so you always want to implement this first to make sure you can actually quit the game okay so there we go we've written a good amount of code already what i'm going to do now is run this code and display mode not set oh okay so this is an interesting error to run into so i'm getting a problem here it's saying display mode not set because i've not yet instantiated my window right remember i told you we need a window or a screen to actually draw on so before i can update the window i need to create it and to create it i'm going to have to instantiate this draw information class so i'm going to go to the top here and i'm going to say draw underscore info is equal to draw information and then what do i need to pass here well i need to pass a width a height and an lst so let's decide on our width and height for now i'm going to go with 800 600 if this is too big for your screen then make it a little bit smaller but this should be a good size to start with and then i need to pass a list now for the list i'm just going to say lst is equal to create starting list and i'm going to pick my values here now be helpful to put them in a variable so i can change them very easily later so i'm going to say n is equal to 50. i'm going to say min val is equal to let's go with zero and let's go max val is equal to 100 and then we're going to pass n min val and maxwell now one thing to notice here is i'm doing everything very dynamically i'm using lots of variables and i'm making sure that if i change one or two values the entire program will update to represent that right that's why i'm putting everything in variables just so it's really easy for me to see where i can change something and so that if i ever have to reuse these variables which we will actually in a second i don't have to hard code the same thing multiple times okay now inside of draw info i'm going to pass lst as the last argument and now we should actually be good to run this and hopefully see a screen showing up so let me run this and create starting list is not defined did i not define that oh sorry generate starting list is what that's called so let's change this to generate i mean generate create pretty much the same thing let's run and there we go okay so we get a window it says sorting algorithm visualization and obviously nothing's showing up because we haven't drawn anything so now it is time to draw something and actually it looks like the x button is not working so let me tell you why it's not working because i see the error so to close this i'm going to have to manually close it i think i can do control c or control alt c what was my button to break this i got to figure this out tools cancel build control shift c okay that's how i cancel my build in subline anyways the reason this is happening is because i forgot to add my type here so you have to say ifevent.type is equal to pi game.quit not just event event has the type property on it so you have to access that first okay let's just try this one more time to make sure i didn't mess anything up let's click x closes the program awesome we can now actually draw the list okay so to draw the list i want to write a function in fact i want to write two functions one function that's responsible for just drawing the general screen and the second function that's responsible for actually drawing the list right the thing that we're going to be sort so i'm going to do a function doesn't really matter where i put it and i'm just going to call this draw and what this is going to take in is draw info okay so we're going to take in draw info and then what we're going to do is fill the screen with the background color of our screen so i'll explain this in a second and then after that we'll update the display and then we will draw the list so for now i'm going to say draw info dot window so i'm accessing my window here and then i'm going to say dot fill and what dot fill takes is a color and it will fill the entire screen with this color now in pi game the way that drawing works is you draw a bunch of stuff onto the screen and then as soon as you want to apply that drawing and actually see it you update the display so what you do first usually at least this is what i do i fill the entire screen with the color to kind of get rid of any of the previous drawing that would have occurred so it's overriding everything on the screen then i draw a bunch of stuff then i update it and then the next time i draw i clear everything redraw it again and continue this is not the most efficient way to do things but it makes it so that if you kind of were drawing a bunch of stuff you're not seeing overlays or shadows or multiple things on the screen when you shouldn't see that you're just redrawing the entire canvas every single frame hopefully that makes a bit of sense we'll see this in a second but for now i'm going to say that i want to do this with the draw info dot background color right because i put background color as a class attribute right here it's equal to white white's this so now i'm going to fill the screen with whatever the background color is and that way if i want to change the background color i just go here change one attribute and we're done okay now that i've done that i want to update directly in here so i'm going to say pygame.display dot update okay so let's just call the draw function and make sure that works and then we'll draw the list so i'm going to go to main and now right under my clock.tick i'm just going to say draw and i'll pass draw info which is an instance of the draw information class great okay now what i can do is run the code and let's see if it's white there we go we now have a white background awesome we can now close okay so now that we've done that we want to draw the list now i'm going to put drawing the list in a separate function because we're going to do some more drawing stuff in here but drawing the list is kind of a separate thing right so i'm going to say define draw list like that i'm going to take in draw info and for now i think that's actually all we need now this is a little bit complicated here drawing the list i will explain obviously as i go through but we have to look at every single element in our list we have to determine the height of that element and the x coordinate of that element and then draw a rectangle representing it and we also want to make sure that we're drawing all of these rectangles in a slightly different color so a different gray right so we can actually see them because if we don't draw them in a different color it's just going to be all kind of squished together so now what i want to do is add the three different colors for my what do you call it blocks rectangles whatever so let's go to draw information and let's create something called gradient i think that's how you spell gradient i'm going to do gradients now this is just going to store three colors which are going to be kind of my gray gradients now i don't think they're really gradients i could probably call them grays but i went with gradients so we're going to keep them so for now the first one will just be gray and then the next one is going to be one and let me look at my cheat sheet here okay 160 160 and 160 and then the last one will be 192 192 192. now i also could put these in variables and call them like dark gray light gray medium gray whatever for now we'll just do this in fact it's probably gonna make sense just get rid of gray actually and just manually hard coat it in because there's not really a point to me having one of those as a variable but not the others okay so there we go these are our gray gradients and now i can use these when i'm actually drawing my rectangles okay so now let's go inside of draw list and what i'm going to do is iterate over my list so i'm just going to say that lst is equal to drawinfo.lst just so i don't have to keep writing out drawinfo.lsd i'm going to say for i val in enumerate lst now enumerate's going to give me the index as well as the value of every single element in my list so this will be good to use when looping through now what i need to do is calculate the x coordinate and the y coordinate for the top left hand corner of this rectangle because when we draw a rectangle in python we draw it from the top left hand corner then we draw it down and to the right depending on the height and the width okay we also need to calculate the color because we're going to have a different gray color depending on what rectangle we drop so i'm going to say x is equal to and then this is going to be draw info dot start underscore x this is the starting x position plus and then this is going to be i multiplied by and then the draw info dot and this is going to be the block width i think that's actually good for x that will tell us where we want to draw our block and if i is 0 so it's the very first block then that means we're going to draw it exactly at the starting x position which is what we want perfect now we're going to do y now y is going to be at this is actually going to be the value multiplied by the draw info dot and then this is going to be the block height however i need to offset this by a certain amount so actually let me load up the program again and just talk about this because it's a bit more complicated that i remember so what we need to do here is we need to draw the taller rectangles higher on the screen right so you can see this guy's obviously higher than this guy now we start drawing from the top left-hand corner which means i need to draw from a higher y-coordinate meaning like a lower y coordinate value because y 0 is up here so y say 200 is where my mouse is right so i need to kind of do the reverse of what is intuitive here i'm going to figure out what the height of this rectangle needs to be and then i'm going to subtract that from the height of this screen and that will tell me the starting coordinate so then i draw it downwards starting from there hopefully that makes a bit of sense but this is going to be a bit different than what i wrote out here in fact it's going to be completely different so what i'm going to do here is write draw underscore info dot height so the height of the screen and then i'm going to subtract that from and then this is going to be a little bit different here i'm going to take this outside of the parentheses and i'm going to say this is going to be the value minus and then this is going to be the draw info dot minimum value so the reason for this is that i can't just use the value itself to actually determine the height of the rectangle the reason i can't do that is because we have a range of values we could potentially have in fact we could have a range of like negative 100 to 0. if that's the range that we have and i just multiply my value by my draw info.block height i'm going to get a negative amount and it's going to give me like a ridiculously high size for the smallest value so we need to actually take whatever our value is and subtract it from the minimum value to determine how much larger it is than the minimum because the minimum is going to be represented as a height of 0 or as a height of 1 i forget exactly how it's going to be but the idea is we'll subtract the minimum value that tells us how much larger we are than the minimum and then we multiply that by the block height and that will give us the correct height hopefully that makes sense that's really the best explanation i can give you next what we're going to do we're just going to look at my code over here is we're going to determine the color that we want to draw with so i'm going to say the color is equal to and this is going to be the draw info dot gradients and then this is going to be at i mod 3. now we have three elements inside of gradients which means we have the indices 0 1 and 2. so when i take the division or the remainder after division of three this is always going to give me zero one or two and all of the elements beside each other will have a different mod three right so like element at position one two and three are gonna have different values for i mod three and so that's gonna allow me to have all three of the elements that are beside each other having a different color hopefully that makes a bit of sense but essentially every three elements we're going to reset and we'll go back to the original gray but for those three elements we'll have the light gray medium gray and then the dark gray then we'll reset and continue that's what imod 3 will do now that we've done that we can actually draw this onto the screen so i'm going to say pygame.draw.rect this is how you draw a rectangle i'm going to pass the position or sorry screen where i want to draw this i'm going to say draw info dot window i'm going to pass the color which is going to be this and then i'm going to pass my rectangle which is going to be x y this is then going to be the block width so draw info dot block width and then draw info.block height is correct but we're going to need to determine how high this block actually is so that we know how far down to draw right because we figured out the top left hand corner position but now we need to figure out how much downwards we want to draw now we could really just do this we could just do height and in fact that will work because if anything will draw off the screen but we will always fill down to the bottom of the screen so hopefully that makes a bit of sense like if the height of our block is 300 then we can just draw a height of 500 because if we draw 200 over it just won't show up because it's going to be beneath the screen so i'm just going to be lazy and go with that for now you could calculate the precise height using the value but i don't want to do that so i'm just going to do this okay so i think that's going to be good for now yeah that should actually be good we can just draw the list like that so now what i'm going to do is inside of the draw function after i clear the screen i'm going to draw the list so let's go draw list let's pass draw info like that and then we'll update the display here and fingers crossed we should be seeing the list showing up on the screen now if i run the code okay so let's go ahead and do this and let's see what we get and it says block width is not defined okay so let's see where i did block width oops i need to do draw underscore info dot block width when i am drawing my rectangle okay so make that fix and hopefully we should be good now let's try this and there we go we can see we have all of our rectangles showing up and let me just run this a few times and show you that it's going to work for different values right because i'm randomly generating the values and we initialize this so we should be getting slightly different sizes for our stacks or blocks or whatever you want to call them okay perfect that is looking good to me now what i want to do is just implement the ability to reset the stack size just so that we can go through a bunch of different options and check to make sure that's working so i am going to now implement a key press for the r key on your keyboard so when you click that it will then reset the uh the list okay so i'm going to say if and then this will be pygame dot event is equal to pygame dot key down and i'm actually going to say if this is not equal to key down then continue so if we're not pressing any key down we're going to continue it just means we're going to go to the next event in the for loop otherwise though so if we do get past this it means we did have a key down i'm going to say if pygame.event.key is equal to pygame.capital k underscore r uh you kind of have to look them up for all of the different keys but this will give you r if you wanted a you'd be like k underscore a if you wanted space it'd be k underscore space with all capitals on the space for all the letters it's usually just the lowercase letter so in this case we'll just go with r and now what i will do is i'm just going to reset the list so i'm going to say that lst is equal to this so we'll say lst is equal to generate starting list n min val and max val notice why i put these variables here now so that we can reuse them again and then i need to set the list on my draw info class so i'm going to say draw info dot set list and then pass lst because remember draw info is storing this list so we need to reset it on the draw info class otherwise it's not going to update when we're actually drawing because look all we're passing is draw info right so now when i press r it should actually reset this so let's run the code and let's see if that's the case okay so when i click r it doesn't seem to be working so let me see what i messed up here and then i'll be right back all right so for some reason i decided to put a preface of pie game before my events we don't need to do that we do need them here before key down and k underscore r but i don't need pie game dot event because i just want to access the event variable so that's the issue i was having so i'm gonna remove those and hopefully now this should be good okay so let me try and okay it still doesn't seem to be working so let me have a look and i'll be right back all right another silly mistake here i really should just look at my code because i'm trying to do this off the top of my head but i need to add a dot type here so i was saying if event is equal to pi game dot key down i can't do that i need to do dot type just like i did here now hopefully this should work fingers crossed let's run the code let's hit r and then there we go we can see we're getting many different stack sizes showing up on the screen exactly what i want perfect okay so now that we have that really what we can do is actually implement the sorting algorithm itself and then start actually kind of drawing the steps in the sorting algorithm that's going to be the most complicated part but we've got kind of the main i guess foundation done for this application and really all we need to do is make it so now we can draw what's happening in the sorting algorithm which of course involves implementing the sorting algorithm itself so the first thing i'm going to do here is implement a key press for space so when you hit the space key it actually allows you to start sorting and then we'll implement the sorting algorithm so just like i did here i'll actually copy this i'm going to say alif because if it wasn't that key r then we'll check it with something else so l if event dot key is equal to pi game dot key underscore space because this is how we're going to start sorting then what i want to do is just set a variable here i'm going to say sorting is equal to true okay so i'm going to go up to the top of my program i'm going to say sorting is equal to false and then this will kind of tell us okay are we sorting are we not sorting and i'm also going to add something here that says and sorting is equal to false double equals to make sure that we can't start sorting if we're already sorting right whereas if we want to reset that's fine we can reset if we're currently sorting in this case we'll actually say sorting is equal to false so if we do reset what's on our screen then we want to stop sorting because we would have changed the list so we'll say sorting equals false okay that's really all we need for that the next thing i will implement is ascending or descending so i'm going to say ascending is equal to true and then i'll implement the key presses to toggle ascending or descending so if you hit a it will be ascending if you hit d it will be descend so let's copy this let's go here we'll just say l if event dot key is equal to c pi game dot k underscore a then we'll just set ascending equal to true so we'll say ascending equal to true like that and then we can go here say alif event dot key equals k underscore d then ascending is equal to false and i'll just make sure that we can't do this while we're sorting so i'll say and not sorting and not sorting okay nice now i actually uh want to wait to the very end to do this sorting algorithm part i just want to draw on the screen the different controls so i'll show you what this looks like but if you look at my window notice how we have kind of like what we're currently doing and then we have reset space a d and the different toggling for the different sorts so i want to actually draw that onto the screen and then we'll implement the sorting algorithm so to do that we need to set up a font so whenever you want to draw something in pi game you need a font and you get that by using the follow do something like font is equal to pygame.font.sys font then you need to give it a actual font so i'm going to say comic sans there's a bunch of options here but comic sans is just always the one that i use then you need to give it a size for now i'll go with 30. now this is going to be my regular font i also want to have a large font and the large font is going to have a size of 40. okay so there we go i've just defined the fonts on draw information so we can access them any place that we're drawn perfect so now let's go to draw and let's actually implement kind of the control text so whenever i want to show text on the screen what i need to do is use a font to render a text kind of surface or object or painting or whatever and then i put that onto my window so i'm going to do the following i'm going to say controls is equal to and then this is going to be draw info draw underscore info dot font and then dot render and then i'm going to put what i want to render so let me actually just copy this in so i don't mess it up okay let's grab it for my other screen so this is going to be r is reset and then i have the pipe and then space is start sorting a is ascending and d is descending i'm going to put a one this is the anti-aliasing just make this one it's essentially like the sharpness of the lines so always make the middle parameter one here and then the color and in this case i just want it to be black so i'm going to say draw info dot black of course you could hard code in black as well but we'll just go with that to make it more readable okay so now that we've actually rendered the font let me see if i can just let you guys see this so it's still on the screen here for a second what i need to do is actually display this on the screen and i want to display this perfectly in the center so i'll show you how to do it so to draw i guess text onto the screen you do draw info dot window need to access your window then you're going to use dot blit blit will just take a surface and blend it onto another screen so that's what we're doing here i'm going to pass the surface which is controls that i want to actually blit and then i pass the x y coordinate where i want to display it now the y coordinate i can just manually set as like 10 or something like 5 so it's very close to the top of the screen but for the x coordinate since i want it perfectly centered i need to do some kind of math to figure that out so i'll show you what the math looks like i'm just going to open up paint so let's go paints like that and we can see what it looks like okay so let's say i have a window that looks like this and i have some text and i want it perfectly in the center of the screen well i have the width of the window which is like w right and then i have the width of my text let's just call this t okay so the way that i actually determine where this coordinate is because that's what i want to determine right i need the top left hand corner of the text because then it will draw going from the right of the top left hand corner the way i determine this is i start by saying okay well the middle of the screen is right here that is w over 2. now i'm just using my mouse so please excuse the massive discrepancy in font size but w over 2 is the middle of the screen now that's fine if my text was say one pixel i could just draw it right here however if i start drawing my text right here then it's going to go off the screen it's not going to be centered so what i now need to do is take t over 2 so the what is it width of the text and then if i take the width over 2 and i subtract it from the text over 2 that actually gives me this coordinate right here so hopefully that makes sense but if you see that we have a width of let's get rid of all this if this is half the width of the text right that's how much further to the left from the middle of the screen i need to go to draw the text perfectly in the middle of the screen that's really the best explanation i can give that is how you draw it perfectly in the middle of the screen that's what i'm going to implement now you could do the same thing with the y if you wanted to but i don't want this in the middle and the y coordinate i only want it in the middle for the x coordinate okay so let's now do this we're going to say the uh not game info the draw info dot width over two subtracted by the controls dot get underscore with over two this is a useful method you can use on any of your text objects just do controls or whatever the name of it is dot get with and then you can divide it by two like i did so this will put it perfectly in the middle of the screen and then if you change what's in here it will automatically adjust okay great so that's controls now underneath that i want to have i guess sorting so sorting is to like change the sorting algorithm that we're going to use so we'll just copy this one in as well so we're going to have i for insertion sort and b for bubble sort now we haven't implemented those yet because we don't yet have the sorting algorithm but that's what i can do and then when i draw this all i have to do here is change a few things so i'll just say sorting and then rather than drawing it at five i'm going to draw it at 35 so it's 30 pixels below the controls right here okay so that's all i need for drawing the text on the screen to draw what we're currently sorting i'll do that in a second because we don't yet have the sorting algorithms but let me run this code and let's see what we're getting so far okay perfect there we go so we have r reset space start sorting a ascending d descending i insertion sort b bubble sort perfect that looks good to me really the last step now is implementing the sorting algorithms all right so now we can go ahead and implement these sorting algorithms now i'm not really going to be discussing the logic behind these different sorting algorithms there's all kinds of videos and tutorials on the internet talking about how these work i'm just going to code them out relatively quickly and then i will show you how we can make it so we draw the steps so let's write a function i guess we can do it right above main and let's call this bubble underscore sort now for any of our sorting functions if we want them to work with our code what we need them to take in here is draw info and then ascending and i'm just going to have a default value equal to true so i'm going to make it so the bubble sort and the insertion sort can sort either an ascending or descending order because we have that as kind of a parameter for our sorting algorithm visualizer anyways for the bubble sort i'm going to say that my lst is equal to draw info dot lst just so i don't have to write out draw info a bunch of times and then i'm going to say 4i in range and this is going to be the len of lst minus 1 and then i'm going to say 4j in range and this is going to be the len of lst minus 1 minus i now we could do it in the other order as well but this will be fine for now and then i'm going to say num1 is equal to lst at and this will be j and then num2 is equal to lst at j plus one okay uh and now we're going to compare the values so i'm going to say if num1 is let me look at my cheat sheet here greater than num2 and ascending so we're going in ascending order then i want to swap these values so i'm going to say lst at j lst at j plus 1 is equal to the reverse so lst at j plus 1 and lst at j this is how you can swap in one line without a temporary variable in python this will just swap the values in the array and then after this i want to draw the list again okay so i'm going to talk about how we can do this in a second for now i'll just leave this commented out but this should work to actually sort the list and then i'm going to do something that's going to look a little bit weird but i'm going to yield true now i'm going to discuss why we need this in a second but finally at the end of the algorithm i will return lst and now all i want to do is make it so this can sort in descending order as well so it's going to look a little bit strange but i'm going to put this i'm going to say if num1 is greater than num2 and ascending or if num1 is less than num2 and not ascending so this is essentially checking the descending case then we will still do the same thing so if we are ascending and number one is greater than number two then let's swap them if we're sorting in descending order so not ascending then if num1 is less than num2 then we can swap them now let me make sure that condition is correct i believe it is awesome now let's talk about this yield keyword so the reason why i'm yielding here is because what i want to do is call this function for each kind of swap so i want to call this function every time i want a swap to occur so rather than having this go through and run the entire algorithm i want it to perform a swap and then yield control back to wherever it was called from and wait to be called again until it's going to perform the next step now this is called a generator this is going to work similar to an iterator like you might have for a for loop and again what this lets you do is pause the execution of the function kind of halfway through and then resume it from whatever this yield keyword came from so yield is obviously different than return yield is going to pause but store the current state of the function so that means the next time i call this generator to run it's going to run sorry starting at wherever it yielded from last time so theoretically i can yield anything that i want i'm just yielding true because that probably makes the most sense but i just want to have the yield keyword so that i can stop the function and then resume it and again you'll see why i want that in a second but essentially this is going to allow me to be able to continue to use the controls like reset um exit out of the screen all of the other buttons because if i don't yield then this function is going to have control the entire time it's doing the sorting and i'm not going to be able to press any other buttons on my keyboard the program can't respond to anything else if this is not yielding okay so now let's talk about the drawing aspect so the reason i pass draw info here is one because we need lst but two because in this function itself i'm going to manually draw the blocks or the list that's being sorted now what i want to do is i want to redraw the entire list on the screen but i want to color the two things that i'm swapping so i want to color j and j plus one in red and in green now you can put them in whatever color you want but that's what i want to do so what i'm actually going to do here is i'm going to go to draw list and i'm going to add one more parameter here which is going to be color positions like that now this is going to be equal to a dictionary and i'm going to pass in a dictionary of indices and then have that correspond with different colors that i want to make them when i drop so you'll see how this works again in a second i know i keep saying that but i can't explain all of it at one time what i'm going to do here though is i'm going to say if and then we're going to say i in and then this will be color underscore positions then color is going to be equal to color positions at i pretty simple this will be a dictionary the index will map to a color and then we will just manually override the color that we set here to either i guess green or red depending on the color that we are drawing we'll do something else as well inside of here which is actually going to be clearing the portion of the screen where the list is being shown so right now what we have is inside of our draw we draw the list after we draw all of this stuff and after we fill the window so that means we're not seeing double or anything because we're filling the window then we are drawing the list now from my bubble sort function here i could theoretically just call this draw function and everything would work fine however that's not super efficient because i don't need to be re-rendering this text every single frame when this is going to be static right this text is going to stay the exact same so instead of kind of redrawing the entire window what i want to do is just draw the list so what i'm going to do here is implement something that's going to clear just the portion of the screen where this list is being drawn and then redraw the list over top of it again so i'm not redrawing all this stuff i'm just redrawing the list every frame okay so let's do that i'm going to add a parameter here called clear underscore background and make this equal to false by default now if this is true we're just going to override this portion of the screen so i'm going to say if clear underscore bg then the clear rectangle is going to be equal to and i now need to calculate kind of the rectangle on the screen that i want to clear the position for so remember we are drawing our list in uh kind of a certain section of the screen right we're going to be drawing it a few pixels padded from the left and from the right and a few pixels padded downwards so that's kind of the rectangle i want to generate here so that's what i'm going to try to come up with now i'm just going to look at my cheat sheet because this is not simple to do on the top of my head but i believe what we want here is draw info dot side pad divided by two the reason we want it divided by two is because the starting x coordinate is going to be half of the side pad for when we're drawing our list then i want this to be draw info dot and this is going to be the top pad because this is where we'll actually start drawing the list from the vertical position from the y coordinate and then after this i need to calculate the width and the height now the width is simply going to be draw info dot with minus draw info dot side pad this will subtract the left and the right hand side pad so this is correct and then i want the draw info dot height and this is going to be subtracted by draw info dot top pad although again it doesn't really matter if we subtract this or not because theoretically if i just draw the entire height since we're drawing downwards any extra rectangle i draw will just be off the screen and we won't see it so i'll leave this in for now just to show you that this does work we don't really need to actually implement the top pad now let's put this on a second line just so it's a little bit easier to see and hopefully you can read all okay great actually let me zoom out a bit and maybe this makes it a little bit easier okay so now that we've done that what i want to do is actually draw the rectangle so i just came up with a rectangle just because it's easier to put in a variable first but now i'm going to say pygame.draw.rect and i'm going to draw this on the drawinfo dot window the color will be the draw info dot background color and then i'm just going to draw this at the rectangle so rather than putting all this stuff inside of here i just put the variable which is actually called clear rect perfect now since i'm doing that at the bottom here i also need to say if clear background then pygame dot display dot update because i'm not going to be updating in here usually because we update right here after we draw the list so if we are calling this directly so we pass clear background equal true then we need to make sure we update the screen as well all right so i think that's it for draw list hopefully that all makes sense now let's go back to bubble sort and let's actually call draw list and pass kind of these new parameters now so when i call draw a list i'm going to pass a draw info because we are going to be redrawing the entire list then what i'm going to pass is color positions now for color positions all i'm going to do is say j is going to correspond with draw info and then this will be dot green and then i'm going to say j plus 1 is going to correspond with draw info dot red now feel free to change these colors to whatever you like i'm just using green and red and you could swap the order too you could have j be red and j plus one be green i'm not really using them to indicate anything specific i'm just showing the two elements that i'm swapping at this step great then i'm yielding true okay so now we have the bubble sort algorithm done now insertion sort will be pretty simple but let's first see if this is actually going to work and call the bubble sort algorithm so what i'm going to do here is i'm going to make a variable and i'm going to call this sorting underscore algorithm and this is going to store the function that's going to represent the current sorting algorithm that we have so in this case i'm going to call it bubble sort i'm going to use bubble sort but we would change this function to be insertion sort merge sort whatever other sort we're using if that's what we wanted to do now i'm trying to write this in a very flexible way so that all you have to do is write another function that takes in draw info and ascending and obviously will have to be tweaked a little bit depending on the sort but all you'll have to do is literally just put the name of the function right here and then that will change the sorting algorithm that's being used for the visualization okay so we're going to say sorting algorithm is equal to bubble sort i'm going to say sorting algo name is equal to and we're just going to hard code this in as bubble sort just so we can display this on the screen and then what i'm going to do is i am going to go to where we start the sorting so it'll be right here and i'm going to say that my sorting algorithm actually this is going to be a little bit tricky here okay so i just made a cut there because i had to think about something for a second i actually want to add one more variable here which is going to be sorting algorithm generator because we're going to use the generator to actually generate or perform the sorting algorithm this is just going to represent what sorting algorithm we want okay so let's now go here and we're going to say that the sorting algorithm underscore generator is equal to and this is going to be the sorting algorithm that we chose and then we're going to call this function and we're going to pass to it draw info and ascending okay so remember we have this ascending variable here this is going to be equal to true by default but we can toggle it to be false and so if we make it false then we'll pass false for ascending and so we'll sort in the other order now what's going on here is we're creating a variable sorting algorithm generator which is going to store the generator object that will be created when we call this function so this is something about generators as soon as you put a yield keyword it makes a function a generator which means when you call it the first time you call it it actually returns to a generator object so it's not going to return to me lst it's not actually going to run any of this code it's going to give me a generator and then for me to actually use that generator i need to manually call the next method on it or iterate over it so this isn't meant to be an entire lesson on generators i do actually have a video on my channel i'll put it up on the screen it's generators explained in python in case this is very confusing you can go through that you could also check out programming expert we have an entire lesson on that as well whole point though again is that when you call a generator gives you a generator object generator object has this next function on it the next function gives you the next thing to be yielded from the generator so the first time we call next it's going to yield true and it's going to perform all of the steps up until this first yield the next time we call next it's going to continue running until it hits the yield again hopefully that makes a bit of sense but if i had a generator like define gen and then i yielded one and i yielded two when i call my next method i know i'm spelling this incorrectly the first time i call it this is going to give me 1. the next time i call it this is going to give me 2. so i would say something like gen is equal to gen or maybe we go g is equal to gen and then i would call next on g that would give me 1 and then i would call next on g again that would give me 2. and then if i try to call it one more time what it's going to give me is a stop iteration exception if i can okay you guys get the point i can't type properly today but stop iteration so it's going to raise an exception and tell me that hey there's no more elements to be yielded and so we're raising an exception to tell you the generator is done hopefully that was like a mini little lesson on generators but let's continue now so now that we have actually created the generator object i want to put something at the top of my while loop here and i want to say if sorting so if we are currently sorting then what we want to do is try to call the next method on our generator so we're going to say try and oops that's not what i wanted i'm going to say try and then this is going to be next on and what is it called our sorting algorithm generator right here and then i'm going to accept the stop iteration exception and i'm simply going to say sorting like this is equal to false okay and then otherwise i will just normally draw so let's explain this here why is this my autocomplete is just being annoying right now draw tab okay there we go so what i just did here i understand this a bit confusing is i said if we are currently sorting then what i'm going to do is try to call this next method now if this doesn't work which essentially means the generator is done i'm going to raise or i'm going to accept the stop iteration exception and i'm going to set sorting equal to false because that would mean okay the generator is finished now if it's not we're just going to keep calling this constantly until we finish sorting the list once we're done sorting the list stop iteration is raised we then accept that we say sorting is equal to false and then we could sort a different list or reset it or do whatever we want but i'm just calling next on sorting algorithm generator which we initialize right here when we start sorting and the way we do that is by using the sorting algorithm variable which i put right here which is equal to bubble sort so bubble sort is the name of the generator function we call bubble sort gives us the generator object we then call next a bunch of times and hopefully by now you get the point so at this point we can try this out we can see if this is going to work or not i have a feeling we'll get a few bugs but let's try it and see okay so i'm just going going to hit space and i see that nothing is happening currently i hit space nothing is happening and i believe that may be because we're not actually oh okay so it did sort but it wasn't showing me any updates on the screen that's a little bit strange let me have a look here and then i will be right back all right so i found the error i'm sure many of you probably saw this but i forgot to pass my other attribute or other parameter here true so if i go to draw list we have clear background equal to false by default i wasn't passing true so we weren't actually clearing the background and seeing the updates on the screen so now if i pass true we should see that because it looked like it did sort the list it just wasn't showing us the live progress so let's try this now let's run the code okay and let's hit space and notice it's showing this to us now we're getting a bit of red at the top the reason for that is that my background i guess i must have drawn it in the wrong location so we'll fix that in a second but you can see that is actually giving us the visualization and there we go that looks pretty good so let's try to fix this now because it looks like i messed this up so let's go to where are we draw list okay so i'm drawing uh the top y coordinate at draw info dot top pad but it looks like we're drawing i guess the the rectangles above the top pad for some reason that's a little bit strange to me why the rectangles would be drawing above the top pad i just want to see in my other code here what i would have put for this and why this isn't working so let me have a look and i will be right back alright so i've just found the fix my apologies for this guys but this happens from recording recording hour-long videos anyways i have a self-adopt block height here and previously i had route now when i round this what ends up happening is that i'm going to have a bunch of pixels kind of being larger than i want them to be because of the fact that i'm going to round values up now i understand this is a little bit weird to comprehend but let's say that block height before rounding is something like 4.55 pixels meaning for every kind of one unit i have i want to draw that at 4.55 pixels high so now imagine i have a 100 units that i want to draw at 4.55 well if i round this value up to 5 that's going to give me an additional say 20 pixels or something like that that i'm drawing additionally which is going to be going into my self.top pad because i round it up so i'm getting kind of a rounding precision error so what i want to do instead of rounding is i just want to math.floor this which is going to put this down automatically so even if not like 4.99 it's just going to round it directly to the floor to make sure i'm never going to be above this top pad there might be a better solution to this but i think math.floor is the easiest so we're just going to go with that because it will still make the scaling correct for all of our values we just won't be utilizing as much space as possible in some situations which is fine so i'm just going to say math.floor however that means we need to import math so make sure you import math at the top of the program now that should be the fix i think that should be good so let's run this here and let's test out our code because we're pretty much almost done so i'm going to hit space looks like everything is working fine and yeah that is uh looks great to me now i'll show you how to speed this up in one second but for now this is a pretty good speed and you can see that we sort this successfully so let's reset using r let's change this to descending we'll have to add our title to tell us what algorithm and if we're ascending or descending we'll do that in a minute but now let's run this and we should be getting it in the opposite order because i toggled this to descending instead of a set perfect that looks good to me nice and quick sort although not really considering we're using bubble sort but yeah looks good awesome so let's reset and yeah looking good okay so now what we will do is we will add the title telling us what sorting algorithm we have if we're ascending or descending and there was something else that i wanted to do that i forgot about uh i wanted to show you how to speed this up yes okay so if you want to speed this up just change your clock dot tick here to be a higher number so watch what happens if i make this 120 now and you will see that we should go a lot faster yeah so when i hit space you can see we're going significantly faster than we were before and if you want this to go at the maximum possible speed then just remove the clock tick now for some of you even when you increase the clock tick to a large number it's not going to go any faster that's because you're being limited by the speed of your processor in this case i have a pretty fast processor so this is running quickly but if you're on an older computer you may notice this happens significantly slower than what's happening here okay so let's add the title now in order to add the title i need to pass a few more things to draw so when i draw here i need to pass the algo underscore name and then ascending as well telling me if we are ascending or not ascending so let's now pass those values when we call the draw function so let's go to draw and let's pass the sorting algorithm name okay and ascending perfect so now we can go inside of here and what we're going to do is just render some text and display that information so i actually want to render this above my controls and my sorting so what i'm going to do is now put these a bit lower i'm going to draw this at 35 and i'm going to draw this at 65 and then the other text that we draw i'll just draw at 5. okay so now we're going to have instead of controls this is going to be i guess title title is fine for now we then want to blit the title again we want this in the middle of the screen so we're going to put this to title but what we actually want for the title is going to be different i'm going to put an f string here and i'm just going to put inside of curly braces the algo name and then this is going to be a little bit weird if you haven't seen this but i'm going to write an if statement that writes ascending if we're ascending and writes descending if we're not ascending so i'm going to say ascending make sure you're using single quotation marks by the way if you use double then you're going to get an error because we surrounded the f string with double quotation marks but i'm going to say ascending if and then this will be ascending else this will be decent perfect i think that's pretty intuitive to understand what's going on there but that's what we have and that looks good now the f string is only in python version 3.6 or above so if you're using a lower version then this may not work for you in that case you can just use a string concatenation if you're familiar with python that should be relatively simple to uh to replace okay so let's try this now and let's see if the title is showing up okay so bubble sort ascending nice now i want this to be a bit bigger so i'm going to use rather than the font the oops not there the large font that i declared earlier so again remember here we have large font just 10 pixels larger and then rather than drawing this in black i'm just going to draw this in green just so it stands out okay let's try this now okay looks good might want to move the controls down a little bit so let's do that let's make this at 45 and this at 75 okay let's run this and there we go that looks good to me so now let's see if i change this to descending okay we can see the text is updating and now all we need to do is implement insertion sort because as we can see our sorting algorithm is visualizing is working properly okay so let's now do insertion sort so insertion sort i do not have memorized so i'm going to have to look at my other screen so please excuse me while i do this but let's set this up so i'm going to say define insertion underscore sort just like bubble sort we need to take in the draw info and the ascending make this by default equal to true then what i will do is say lst is equal to just like before drawinfo.lst and i will set up a for loop so 4i in range this will be 1 and then the len of lst then i'm going to say that current is equal to lst at index i i'm going to say wow true and then i'm going to write the two conditions for if this loop should let me swap something based on if i'm sorting an ascending order or a descending order so i'm going to say ascending underscore sort is equal to i greater than zero and lst at i minus 1 is greater than current and ascending i understand that's a lot there but we're going to copy this now and do it again and i'm going to say descending sort this time okay descending sort this time it's going to be i greater than 0 and we're just going to swap this sign and say not ascending so these are kind of my two conditions for if i should be continuing in this while loop if you're not familiar with insertion sort again watch a tutorial on it or something i'm not going to explain it in this video but the point is if we're ascending then this is the condition and if we're descending then this is the condition and i'm just writing them in variables so it's easier when i do this next check so i'm going to say if not and then this is going to be ascending sort or not descending sort sorry this is going to be and not descending sort then i want to break otherwise though i'm going to do a bunch of swaps so i'm just checking if either of these conditions are not true if one of them is true i will continue if both of them are not true then i don't need to do any swaps so i break okay so i'm going to say lst at i is equal to lst at i minus 1. i'm going to say i is equal to i minus 1. i'm going to say lst at i is equal to current that's the variable we have defined right here and then i'm going to say draw lst because we've just done our swaps and i'm going to pass draw info i'm going to pass i and then this will be draw info dot green and then we will pass i minus one and this will be draw info dot and then red okay then we need to pass true and i think after we yield true here and we finally return lst we should be good now i understand i just kind of speed coded that out so i'll walk through this quickly we have our list we have our for loop current is equal to lst at i and then while either of these two conditions is true based on if we're sorting in ascending or descending order we're going to perform the swaps so we're going to say lst at index i is equal to lst at i minus one i is then equal to i minus one so we're actually modifying this iterator variable right here and we're saying lst at i which we just changed here is equal to current which is this value so just moving it in the list then we've performed swaps here so the two values that i want to highlight is i and i minus 1. now this needs to be in capitals my apologies i'm going to do this in the other order i'm going to say i minus 1 and then i like that just to be consistent with what we did here okay then i'm yielding true the reason i'm yielding true is because i just did a swap so every time you do a single swap you should yield just so that you give control back to the main loop so that you can then press a button reset pause whatever it is that you need to do okay so now we have insertion sort i think this is just good to go so let's now look at how we can swap between the two so what i'm going to do is add some buttons here one that is for i insertion sort and then b4 bubble sort so let's copy this let's paste this in twice and rather than pi game underscore d this is going to be i i don't care if i'm sorting or not actually maybe we won't let them swap it if they're still sorting so we'll leave that in and then if they hit i then what i'm going to do is say that the sorting underscore algorithm is equal to insertion sort and then we'll just change the algo name so sorting i'll go name okay and then the name will be insertion sort like that okay nice now let's copy these into here let's change this key to be b and then of course we just need to adjust this so that this is now going to be bubble sort so bubble sort like that and then this will be bubble sort okay that's actually all we need to do because now we will just change this function that we're using for the sorting algorithm and the sorting algorithm name everything else will automatically be handled for us and just like i was talking about before all you need to do to implement another sorting algorithm here is write a function that acts as a generator so you just need a yield keyword whenever you want to draw something make sure you take in draw info and ascending and then you should pretty much be good so long as you're calling draw list at the appropriate time in that sorting function now this has to happen in place if you're not doing this in place then you're going to have to kind of come up with a different visualization technique because this is only going to work for in-place sorting algorithms anyways let's run this now and see if this works to toggle the different algorithms so i'm going to click b i'm going to click i now we're in insertion sort ascending let's change it to descending and let's run this this looks different than bubble sort i think yeah it looks like insertion sort to me but let me just confirm and we'll run bubble sort and see if we get it differently okay so let's reset let's go to bubble sort and let's run this okay perfect so bubble sort is working differently than insertion sort which is what i expected awesome so i think with that said that is going to wrap up this video hopefully this gave you a good kind of platform to build a sorting algorithm visualizer there's a few optimizations that could be performed here not everything is completely perfect but i think for a youtube tutorial and again giving you kind of a foundation and base this is a really good starting point if you guys have any recommendations for how to improve this please leave a comment down below it's unlikely i'll make another video on this but you could help someone else out which is always appreciate if you guys enjoyed the video make sure to leave a like make sure to check out programming expert from the link in the description use code tim for a discount and i will see you in another youtube video [Music]

Channel: Tech With Tim

Views: 9,920

Keywords: tech with tim, python sorting algorithm, sorting algorithm, visualizer, visualizer tutorial, pygame, pygame setup, bubble sort, what is bubble sort, insertion sort, what is insertion sort, programming expert, how to make a sorting algorithm, python, python tutorial, python generator, how to bubble sort, how to insertion sort, coding a sorting algorithm, programming a sorting algorithm, what is visualizer, how to use visualizer, tech with tim sortingn algorithm

Id: twRidO-_vqQ

Length: 75min 36sec (4536 seconds)

Published: Sat Dec 18 2021