Visualizing Sorting Algorithms in Python

[Music] what is going on guys welcome back in this video we're going to visualize sorting algorithms in python we're going to take something simple like bubble sort or something a little bit more complicated like merge sort and we're going to visualize it using matplotlib so the focus is not going to be on the algorithms themselves uh but on the visualization on the animation of sorting in python so what we're going to do is we're going to open up a new python file we're going to open up cmd and we're going to install if you don't have it already matplotlib and numpy those are the two libraries we're going to need for that numpy just to create a list and math.lib to visualize the sorting we're going to write the sorting algorithms ourselves if you want to have more information more content on the algorithms themselves you can check out my algorithms and data structures tutorial series where i have a part on sorting algorithms and i also have i think a specific video on the merge sort algorithm in python so what we're going to do first we're going to import matplotlib dot pi plot as plt and we're going to import numpy snp and now we're going to basic bubble sort algorithm so we're going to say list equals np random.randint from a range to zero from zero to a hundred we're going to generate let's start with 15 numbers for example and then we're going to just say x so the x values are np a range from a range from 0 to 15 with a step size of one maybe we should have a amount variable here that we're going to set to 15 then we're going to replace that with a mount i'm going to place that with a mount as well and what we're going to do now is we're going to just say n is going to be the length of the list and for i in range and we're going to iterate through the whole list and inside of that of course we have another loop this is the basic bubble sort quadratic runtime algorithm so for j in range and this goes from zero to n minus i minus one so depending on how much we already processed uh what we're going to do is we're going to just plot the list so we're going to say plt bar so each stick is going to be one number at the respective position we're going to pass x as the values here so that we have some ticks and we're going to pass the list as the numbers um and then we're just going to say plt pause this is going to cause an animation so 0.01 for example just don't pick a too small number because then you're going to see a wide screen and nothing is going to happen um and basically what we're going to do then is we're going to clear the screen after every plotting so that we don't have all the bars at the same time so we're not overriding the previous plots we're going to call a clear figure so clf and once uh this is done we need to actually do the check so if the item at position j is larger than the next item at j plus one then we're going to swap these two numbers so swap j and j plus one so we're going to say j and j plus one is equal to j plus one and j again we're not going to talk about the algorithm necessarily here itself we're just going to plot it and once we're done in the end we want to call it show so when i run this now we should be able to see the sorting happening as you can see this is how bubble sort works we can see that it takes always an individual stick compares it and then moves it to the right until it finds something that is larger then it takes that moves it to the right and after some while it's going to have sorted the whole list now the animation is very slow you can play around with the pause time um but essentially this is now done and when it's done it's going to just stay there and do nothing it's just going to show you that now of course we can do that uh let me first play around with this time here maybe we can speed it up a little a little bit um yeah a little bit at least so this is what you can do and of course you can do that with ten values you can do that with a hundred values so i can run this on a hundred we're not going to wait for it to finish but that is how you could do that there you go and of course if you want to be creative what you can do is you can also pass an array or a list with uh different colors so essentially you could say um take the one that we're currently comparing and make make it red or something so that we always know what exactly it's moving that is how you would visualize a simple bubble sort algorithm all right so let's go ahead and do the same thing for a merge sword what we're going to do here is we're going to copy the code because again i'm not going to explain everything about the merge sort i have a video where i go through all the individual lines of code in this video i just want to add uh the animation stuff so i'm going to copy the code that i already have in a video so that is the code for a simple merge sort you can see that we have the merge sort function itself it splits the list up into left and right then uh it calls itself recursively and then in the end it merges so a merge sort takes a list splits it splits it splits it until we have individual elements then it merges them together and the list is sorted again i explained this in multiple videos in my algorithm course and in the merge sort tutorial so you can check that out if you want to what we're going to do now is we're going to visualize that so uh we want to find positions where we can actually go ahead and add some animation so one would be here before we start the recursive calls we can just say plt bar and we're going to pass list of range 20 depending on the numbers here we have 20 numbers we can tweak that number again we can create a variable amount and we can call it 20 for example we can replace this by amount and we can replace this by amount and i think we don't need anything else so we're going to just plot here again those are the x values and after the x values we're going to also plot the number list itself which is the parameter of the list then we're going to say plt dot pause again 0 0 1 and then plt.clf now this happens before we start the recursive call once the recursive call is done maybe you want to do it again and then once the merging is done so once we merge these split up lists again for this particular iteration keep in mind this is recursive uh so it's going to happen a lot of times we want to also plot it again i'm not even sure if that's necessary we're going to see in a second if it works without it as well uh and once we're done in the end once everything is done we want to also have the final result so what we're going to do is we're going to print the numbers and afterwards we're going to say plt bar again list range amount and this time just numbers because we have the external variable so not the parameter we're outside of the function and then plt dot show so we're not going to do any animations here and when we run that you should see the process of a merge sort you can see that the typical thing is it takes individual lists sorts them and then it merges them together you can see the left part is already sorted then the right part is sorted and then they're merged together so you can see now there you go it's merged together now let me just see if i comment that out here was it that if it's still going to work because i don't know if things change that much actually not this one sorry this one don't know if if things changed that much but i think they could so let's see looks actually kind of fine yeah so you can see this is how it works maybe we can speed up the animation by adding a zero here and by adding a zero here and we can also increase the number amount to i don't know 50 or something and then when we run this hopefully we're going to be able to see the merge sort yeah so it's going to take a while uh it's not the the fastest animation i'm not even sure how we can speed that up there's certainly some parameters that we can pass but as you can see here this part this left part is sorted then it's merged together with the right part that was sorted but it still is just the left part of the whole thing so we have sub list it's it's merging uh it's splitting it's merging and so on you can see this is sorted disassorted now this is sorted they're going to be merged together and then the whole thing is merged together and this is how you visualize sorting algorithms in python so that's it for today's video if you enjoyed i hope you learned something if so let me know by hitting a like button leaving a comment in the comment section down below and of course don't forget to subscribe to this channel and hit the notification bell to not miss a single future video for free other than that thank you much for watching see you next video and bye [Music] you

Channel: NeuralNine

Views: 18,353

Keywords: visualizing sorting algorithms, sorting algorithms python, python animate sorting, sorting animation, animating sorting algorithms, visualize sorting python, python sorting visualization, merge sort python visualization, bubble sort python visualization, visualizing bubble sort python

Id: IRkvlqPBqNg

Length: 9min 23sec (563 seconds)

Published: Tue Nov 02 2021