Transcripts
1. Introduction: Good day, ladies and gentlemen on Welcome to this video elections Siris on an introduction to algorithms in Python. My name is Harmon. I am a video game designer and developer currently working at Sea Monster Entertainment in Cape Town, South Africa. I have worked in the I T industry for a while now. I used to build giant e commerce systems, but found that game design was more to my liking. And I really enjoy teaching. I studied computer science and multimedia at the University of Pretoria and have always been fascinated with how algorithms work on the brilliant minds behind these data structures and algorithms. In this video series, we're going to be taking a look at sorting algorithms specifically. So why should you learn sourcing algorithms? So they're a great place to start when learning algorithms. So you may be saying, Why should you learn so single rooms, they're already included in many programming languages. Well, this is true, uh, python Say, for instance, has the Tim sold algorithm. This is more of an academic exercise. Teoh give you a foot in the door on how Albertans work. It gives a person more insight into how these systems actually function on its relevance to real world problems. And finally, it's because they're pretty needs them. Very cool. So first we're going to learn about computational complexity and the efficiency of algorithms. Then we're going to be doing the most basic source, that bubble sort. Then the insertion sort. After that, we'll take a look at my personal favorite, the merge sort, and finally, the semi appropriately named Quick Sort. Each lesson is broken down into a description, a breakdown of the complexity of the Oliver, them best average and worst case. Then we take a look at a visualization of Halabi function performs, followed by a dip into coding that algorithm Onda. We will wrap that all up by doing a visualization a gain as you will then know what's going on behind the curtain. This is for students who are interested in algorithms on the subtleties of computer science . Whether you're just starting out or are old hat, it will be something inside of this video election Siris for you
2. Computational complexity: good day, ladies and gentlemen, and welcome to this lesson on Big O on computational complexity. The reason why we need to learn bigger and computational complexity is because it's the way that we measure the efficiency off the algorithms that we use. So it is very important in computer science and specifically insulting algorithms to define what is a good or a bad over them. The Big O notation is used in computer science to describe the performance or complexity. Often algorithm Big oh specifically described the worst case scenario, yet it can be used to describe the execution time required or the space used either in memory or on disk by the algorithm, specifically with sorting algorithms. We can also use it to describe an average case or a best case scenario, as sorting algorithms can have an average worst or best case pre sorted state. What I mean by that is, if we have an array off five numbers, that is 38216 That is completely unsalted, right? But it's not completely in the reverse order, which means that it would be an average case scenario. Worst case scenario would be if it was 54321 The reason why that would be worse is because the algorithm has toe actually reverse that entire array. So that would be the worst case scenario. Fort Best case scenario would be 12345 which means that the arrays actually already sorted , and we're just checking to see that it is. As a programmer, I found the best way to understand Big 0 30 is is through code, and we will be doing that throughout the course. What I'm going to do is describe to you the different states off big o on. You'll see them cropping up here in that first we have 01 So no one describes an algorithm that will always execute in the same time or space, regardless of the size of the import data. So that is extremely efficient. It's amazing, Andi, there are very, very few sorting old rooms that can actually pull off on one. Then we have Oh, and so O N describes an old rhythm whose performance will grow linearly on in direct proportion to the size of the input data set. What I mean by that is, if we have an array off 20 items, right? If we add another ice into it, the processing required for that Isil will grew only linearly. Whereas as we will see later, with Owen squared, it grows exponentially. So that's represented in this craft we hear in the yellow is that as more data as more items are added to in this case, on a rate, the computational complexity of it increases linearly. I will get to logarithms such as N log end, Andi Log and Nana. But first, let's go through 20 and squid. So Owen squared represents an algorithm whose performance is directly proportional to the square off the size of the input data set. So this is common with algorithms that involved nested inspirations over the data set. Deeper messages. Rations will result in O. M. To the power of three or o end to the powerful etcetera, etcetera, etcetera. So this is very inefficient. Reaction really wants to to stay away from this. So over here we can see oh, and square in these in this video, Siri's where that is the worst computational complexity we're going to see. We're not going to see 02 to the power of end at all because to be entirely honest, if sorting over them is that inefficient, we just don't use it. We don't even study it. Let's speak about to end. It denotes an old rhythm whose growth doubles with each addition to the inputs. Data set. The growth curve off 02 to the power of and function is exponential, starting off with starting a very shallow and rising meteoric Lee. Let's take a look at logarithms, so logarithms are slightly trickier to explain. So old log n refers to a function or older them or stepping all over them, working in an amount of time proportional to the lover of usually a base to in most cases and all the examples that we're going to see in the future. So the most common attributes off a of logarithmic runtime functions are that the choice of the next element on which to perform some actions is one of several possibilities. Andi again will only and only one will need to be chosen or the elements on which the action is performed are digits off. So 00 log enemy here is ridiculously efficient, not as efficient as 01 but certainly more efficient than the linear o n. And then oh, and look, and it's actually pretty big range over here. But it is still a better computational complexity than say, Oh, and squared. We're gonna be delving much more deeply into this concept in the next few videos. Stick around for that.
3. Bubble sort: Hello, ladies and gentlemen, and welcome to this lesson on the bubble sort. So let's hop right in there. What is the bubble sort? Well, the bubble sources one of the most basic sourcing a logarithms ondas, the simplest to understand, which is why we're going to be starting here. It's basic ideas to bubble up the largest or the smallest elements, depending on whether you're sorting or reverse sourcing in the second largest in the third and so on. It's the one until the end of the list. Each Elements takes a full sweep through the list to find itself in its correct place, So the ball sourcing is a terribly inefficient algorithm. Andi People asking Why, why you learning the bubble sort when already programming languages such as python already food. Excellent sorting older such as Tim sort on. This is done. Maura's an academic exercise to not forget the basic principles off sorting. So the bullet sources, I said terribly, terribly inefficient, with a worst and average case complexity off oh, and squared, which means the Mawr elements that are added to the array. The levee breach of the processing time rose exponentially. Interestingly enough, though, it's best case and are where all the elements in the array are written. Sorted is O. N, which means it just needs to run through the array. What's which is pretty cool for testing if the arrays already sort of, but not so great in actually sourcing the array. So here I have a website sourcing the 80. I highly recommend you check it out. It's a very, very interesting resource when you're learning your different sorting algorithms that it's got a whole host of them. I'm going to be using this throughout all my lessons. So we have a completely unsorted very 09328614 five on seven. So essentially, how the ball so it works is will compare to adjacent partners. In first case is going to be zero and nine. It's going to see if they are in their correct positions. If they are not, it's going to flip them around. In this case, nothing will happen. But when nine is compared to 39 and three, we'll flip around and the next you're compared now nine, because it is the largest in this array will continue bubbling up all the way until the end of the list. Then, as we go through gets, H and H will continue bubbling up, always to right next to nine, then six, etcetera, etcetera, etcetera. Their work. Let's take a look at how that works. Okay, so nine flips over and just carries on, bubbling off, bubbling up all the way until the end off the list and back to the beginning. Three. And to switch agents six. Which says. You can see it's just these comparisons between these pairs toe. Stick them in the right position, and that's usually inefficiently, but it's doing it, and then we go there. We have our sorted list or rate, so I'm going to bring us back to this visualization. Now let's first jump into some code to see what's actually going on behind the curtains. I have this python file or a set up sorting DuPuy instead of my sourcing older them's folder on just that. We can use this the same file for all the different sourcing old rooms that we do. In this lesson, I'm going to oldest in this way. I'm going to say, import random, uh, on. And let's create the array that we're going to be sourcing is random items. Let's populate this already with random grand ins Oh, let's say minus 52 100. So we're going to create random integers between minus 50 on 100 four on a ray off a length off 20. Okay, so just that we can test the test the algorithms away at the bottom of the documents over here. I'm gonna say, Prince, before random items. So that's going to Prince The unsourced array. They were going to call the sourcing ordinary them of choice. In this case, we're going to be calling the formal source, which will implement now and plus random items through to it and prince after, and that is just there to make sure about the older than works. So let's start implementing a bubble sort death, local sorts, passing through these items. So the first thing that we're going to do over here is actually run through the entire rate from zero to the length off items sell a safe for I in range. Thanks. Oh, items. Next, we're going to run through this entire range again, but we're going to not hit the end of it because we know that the largest element in this array is already at the end off. So for J range off make items minus one minus I, which is this variable? Then we're going to say, if items of J is greater than items O j plus one. So essentially, that's the comparison between the two elements to check which one is the greater of the two , and then we're going to switch them. Now there's two ways to switch them. Traditional programming languages. You would create a temp variable and medical it temp item is equal to items O. J. And then we set vitamins O. J people two items off J plus one and then says items O J +12 temporizing. So that's very verbose. And I don't like it very much on Python has a pretty cool way of sourcing this out, sir. Let's take a look at what that is. Well, say items of J comma items R J plus one is people two items off J plus one my sins. O Shea. That's gonna do exactly the same thing. And it's just a lot more elegant till the patent and read. So let's take a look at whether our little bubble sourcing algorithm over here functions as needed. I'm already I've opened up my terminal over here, and I am already inside of this sourcing over Holder inside of that folder is sorting dot high. So let's run this and currently running Python three, but hyphen two should work perfectly fine. Okay, Week up. So before we have negative six negative 35 going all the way through completely random integers between minus 50 and 100 on after it looks like everything is in order, going from minus 50 all the way through to 90. So we know that our little algorithm has done its job. Let's take another look at this visualization now that we know what's going on over here. So that's I should just step through it. Okay. So compares. Nine and three and nine continues bubbling up all the way until the end of the list. And then three bubbles of this h continues bubbling up all the way until the end, and six bubbles up all the way until right next to seven. And now we just need to get that test you want into its correct position. Andi! There we have it. Ladies and gentlemen, the bubble source. Thank you very much. I will see you in the next lesson.
4. Insertion sort: good day, ladies and gentlemen. And welcome to this lesson on the insertion sort in the basic sourcing algorithms and pipe in Khost. So let's hop right in the insurgents off works by taking elements from the unsorted list and inserting them at the right place in a new sort of list. The sorted list is empty. The beginning. This is the total number of elements in the new and the old list stay the same. We can use the seamless to represent assorted on the unsorted sections. So essentially, what this means is we're going to, if rate along, comparing the different partners be completely adjacent elements until we find one that isn't in the correct place and move it down into its correct position. Essentially, doing switches like we saw on the bubble sort is like a bubble down whenever we find certain positions element. So let's take a quick look at the efficiency and then do a visualization. Thea Efficiency off the insertion source is also enough. Break. This is another one of those academic sorts is that the worst case performance is O. N sweat, both on comparisons and swaps. The average case performances Owens Square as well. On the best case performs similar to the bubble sort is OM, which means that everything is in the correct position That only has to operate through the list once. So let's take a look see on how this works. First of all, we're going to compare one with nine. We will see that they are in that correct physicians. Then I was going to be compared to eight. They will switch around, then nine is going to become her to full now for was nothing. That's correct position. So it's going to be moved into place, is going to be compared with eight and switched around and then we move all the way back to nine and two and two isn't in its correct position. So we're going to move down the list and again. There we go so you can see that you can see the trend of here. Zero will have to move all the way down to the bottom of the list. Says it's not in its correct position, and I'm just going to speed this ups now that you have the gist of what is happening over here. We have six moving down three moving down all the way down to the beginning and then fire when we put next to six on seven will be stuff in its correct position. And then we have the source of list. So So let's take a look at the code. Over here we have the also from last time. Let's define a new function insertion. So just takes in the list of items. Don't say so just to make sure that we don't forget this, I added insertion salsa here. So insurgents both will be called when the file is running. First we need toe is race through the entire rate from one to the length This next we're gonna set J people to I The reason why we're setting J ableto eyes just for us to have the position while we moved up. So So while J is greater than zero, you just not the first element. And Bison's off Jay or less than Isis is off. Licence of J minus one. Okay, so this comparison of here is checking to see if, uh if the neighboring elements are in their correct positions and if they are in the incorrect positions, we're going to switch them around as we didn't bowl stops. We're gonna say items of J come out so j minus one and you'll see we're using J minus one instead of J plus one, as we didn't the bubble source from The reason for this is that we're actually doing the comparison backwards so we can carry on switching these into that correct physicians. Tyson's Off J minus one items off, J says. It's twisting around, and then the last and probably the most important part is this. Jay is minus equals one. So what that's going to do is that's going to move the index down while these elements aren't in the correct position. So checking to make sure that we're not right at the beginning, we're checking to make sure that these things are in order. If they're not in order. What we do is we switch them around and move down, switch them around, moved up. Okay, so let's take a look see at how those rooms Okay, so let's run, uh, sorting. Don't And again this friends of the pipe in two and three there we go Soon we have a Unsalted lists 97 85 3 42 21 Onda. We have the after list, which all looks like it has been sorted on it and is in its correct position. Just in case you weren't around for the last lesson, we jet. We randomly generate a list off 2028 inches between minus 50 on 100 that is the the Array that it's sorted. Let's take a quick look at sorting that 18 to see a visual representation of this now that you better understand us. All right, so nine moves in full move status correct position to moves all the way down to its correct position as well, and zero moves all the way through. That's that wild on the deaf, emitting off the J on a three years all the way down to the beginning as well. Five. Into this correct position on finally seven into its correct position. Well, I hope this gives you a much better understanding off how the insertion sort works and also gives you a better understanding of how sorting algorithms in general work have to see you in the next lesson. Have a great one
5. Merge sort: good day, ladies and gentlemen, and welcome to this video on the merge sort in the basic algorithms in Python video, Siri's Let's hop right in the merge sort. It works by subdividing the list into two sub lists, sorting them using merge, sort to recur Siple and then merging them back up. As the Recursive Poll is made to subdivide each list into a sub list, they will eventually reach the size of one, which is technically a sorted list. So we're going to have a nice long list of integers on. We're going to subdivide that into two smaller lists to smaller lists to smaller lists until we have individual integers. Then we're going to use the recursive call to merge them together on stick them in the correct place as they go. Let's take a look at the computational complexity, so the computational complexity off the emerge source in the worst best on average cases are all o n log, and you should remember from our video and computational complexity that this is not terrible, such as and squared. But it's not rich. It's fair. It's a quick look at how the merger so it works so as we have in the image over here, we've got a unsorted array of 38 27 43 39 82 and 10. We split that array up into two, separate to raise or to sub lists, using a recursive cool that's 30 age 27 43 3 on one side and 1982 and 10 on the other side , and we subdivide each of those lists as well on. We carry on subdividing until we have got individual elements all the way through. Now the request of Cool will merge them back up again while doing comparisons to see which element goes where. So 30 18 27 are merged and compared to each other. So we've got 27 38 43 3 are compared to each other, and it ends up as a sub list off three and 43 the same is done here with 1982 and finally 10 here. Honest lonesome. Then we have these sub lists merge together to create these greater sub lists on Finally, these two sub lists merge with each other and they are all sorted in the correct order 39 10 27 38 43 on day 82. Let's take a quick look at sorting Done 80. Sorting that 80 as I've mentioned my previous videos is a fantastic resource for visualizing sorting algorithms and a highly recommended you check it out. Sorting diet. He may not be the greatest way to visualize the merger soul, but I highly recommend you go and take a look. We're going to run through it later, right after we step into the code. So we've got our public sort and insertion sort from the last time. Let's define a new function of it here. Cold merge source takes it an array of items on Let's go. We're going to say if the length off items is greater than one, then we select the middle, which is the length off items divided by two. See anything a little equals over them and we have the left most. The left Summary and Python has a nice way of defining the left summaries items from zero to the midpoint, and we have the right summary, which is ITV. News. Off to the end is a lovely little expressions in python and I highly recommend you do an introduction to Python course just so that you are very familiar with all of these fanciful tricks. Okay, so here's where the rickerson starts happening inside of inside of this function, we are actually going to cool merge source again with the left summary, and we're going to call merge, sort with the right summary. So essentially, what's happening over here is going to carry on happening and carry on happening while the length off licence is if the length of items is greater than one. Okay, so now we are going to merge the left on the right list. So we have left, right? It's equal to zero is your. That's just a nice way to define this. Those indexes going to say, or I in range length off items were running through the entire ray. We're gonna say left value, find this defined. This variable is equal to left at the left index. If left index is less than the length off left on, if that is not the case else, No, let's do the same for rights. We say right value is equal to the rights array at index. Are if if the if the right index is less than the length off, right, Because we don't want Teoh go over and again, we're gonna say else no. Were you to say if left value exists and right value exists and left value is less than right. So this is where the comparison start being made or if right value is none. Okay, so the reason why we're doing this is because there are chances that there is going to be a single instance on either side off the list. You're gonna say, If that's then it's items. Oh, I since we're still stepping through here is equal to left value. All right, so it's sticking it into that better ring. We're going to say left blesses people to want just implemented by one so we can carry on stepping through the left or right. So now we're going to do the same for the other side. We're gonna say we're gonna say if left value and right value, make sure that they exist and left value this time is greater than or equal to right value . You're gonna say that or left value is none of which is set up over here, then we're gonna do the same movie here. Items all I is people too bright value. And then we increments our index both, and this is just a bit of a check. We can stay. Raise exception. Hood knocks merge, and it's making it more descriptive. Sub arrays sizes do not match the main array. Great. So that's the code. Let's take a quick look through it again that this is a request of cool. We're going to see us going through the array again again in smaller and smaller increments . If the length of items is greater than one and refining the middle points, we're creating a left and right array, and then we are calling the merge sort on the subway raise. Furthermore, we're setting an index for left and rights at 00 Then we're going to run through for I am reigns, not rage for the length off those items were going to have. The left value is equal to the value off left at all index. If the index is less than the length of left, just make sure that it's inside. It's inside of that summary else. Left value is equal to none Which we're going to be checking here. Same with right value. It's going to be on the right Summary at index our If our is less than the length off the right separate us, our value is equal to not. And we're gonna do the check. Say, if left value on right value exists on left value is less than right value. This is that comparison. Or if right value is none, then we're going to call. Then we're going to set items of I equal to the left value an increment left value. Same happens of it here, just on the right hand side. And if any of that fails, we're going to raise an exception saying could not merge. The separate sizes do not match the main rate. Okay, let's run in terminal over here. Hyphens sorting dot and run. Okay, so we have the unsorted list of the top, which is a random array of length of 20 which each integer is randomly between minus 50 and 100 afterwards we have a perfectly sorted list. Fantastic. I hope that this has given you some valuable insights into murderous loads. Algorithms in general on how Rikers works. See you in the next video.
6. Quick sort: good day, ladies and gentlemen, and welcome to this video on the quick sort. Let's get right to it. The quick sold works by first selecting a pivotal element from the list. The pivot elements is quite fundamental in the quick sort on, the selection of the prophet element can increase or decrease the computational complexity of it. So the pivot element we're going to be using is going to be the direct center off the list or array, then creates two lists, one containing elements less than the public and the other containing elements hired me. It then assaults the two lists and joins them with the perfect in between, just like the merge sort. When the lists are subdivided to lists of Size one, they're considered already sorted. Also, just like the merge sort. We're going to be using Rikers in yea, the efficiency off the quick source in the worst case is O n squared, similar to the bubble salts and not very efficient. The best case and average case performances R O N log and similar to the emerge sort, which isn't bad. It's not good, either. It's fat. Let's call it fair. Let's do a visualization of the quick sort. Now, as with the merge sort because of everything that's going on behind the curtain of Rikers in it may not make a lot of sense. So first, what happens is we select a pivot point. This is the first is aeration through it, and we're going to dig into the code, so you'll better understand what's happening of him. It finds thesis enter of puppet, and then it's It switches those two, but it doesn't actually switch them. What's happening behind the scenes is it's putting the six into the less than the profit array and is putting the nine into the greater than the pivotal Ray. Assuming that prove it over here is five. Next. As we step through, it switches seven and one and again, when I say switches, it means it puts one into the less than a rake and put seven into the Ranger than Rick. Then we have full put into the less century and six put into the greater than terrain on. Finally, we have 25 switch over each of them, select their own pivot point all the way down, and then those to switch over and As you can see, it slowly starts creating a socialist, and finally seven and each get flipped over on. There. We have the sorted list again. This isn't the best utilization of that. Let's take a look at the code, and I think you will better understand it. So here's the sorting DuPuy file we set up for the previous couple of lessons. It's got a random items ready, which is an array of 20 elements long, each of them randomly generated. Between minus 50 and 100 is to find a new function of it here, called Wick Sorts. Protects in the list of items and taking in the list of items is very important because we are going to be calling them inside of the function because it is regressive. I've also called quick sort down here to make sure that that it is the function that is called when we run the sorting the high file. All right, great. So first things first, as with the merge sort were going to say if length of items is greater than one, because as were subdivided, we wants to stock. Next we select the private index again. This the selection of the Pivot index could be a complicated function in of its own to try and find the correct place for it. But in our case, and for demonstration purposes, we're going to have it as the length of the rate divided by two so dead center. Next we create smaller and larger items raise on. They started out as empty and will be populating them nature. Larger iTunes is people to record varietals. Fantastic. So here's where the magic starts happening. It's a four I. I was going to be the index that's going to hold our place and thou that it was the value off the thing that we're going to be enumerating group the numerator thing through brilliance of items. So again, I holding the index val containing value. You say you I is not people, too haven't index because we don't want the actual covets to be switching. Then if bow is less than icings off within the next, two were doing the comparison to see if it's great to them or less than eight index on, because value is less in the next, take it and put it into smaller items and and then if it is not less than but is in fact greater than or on not equal to, because we're doing that check over there and safe else. Larger Iceman's does a pendant value fantastic, so this wouldn't be a recursive array without a recursive cool. It would just run through it once, and you have a tiny bit more sort of us. Actually, it would just be a single element that gets stuck into the suburb raids Nazi sorts, smaller items. So essentially, what's happening there is We're going to be quick sourcing each individual answer each separate all the way down. So each separates elects its own covet index. It creates a small license and larger icings ray on and each of these then get some sort of that sort France. It sort large, arise Mrs Well, and then finally, what we're going to do is we are going to say items equal to smaller items, plus the of it invests plus larger items. So then that just stitches it all together at the end. So we have smaller items, and then in the middle we have index elements, and then we have the larger items. So let's just take a look at it from the top. We're going to make sure that the length of each of them is No. One. We're going to select a pivot index, declare smaller and larger Ice Marie's and then we're going to run. We're going to enumerate through the items on. We're going to stick them into smaller or larger raise, depending on where they should be. And finally, we're going to core quick, sort on each of those summaries. Let's take a quick look, see if this works. They have my sorting P. WiFi on. I'm going to run it, I thought, sorting up high. And as you can see, we have a unsorted We haven't unsorted most. 28 26 93 minus two on after we have a completely sort of rate from minus 50 to 98. Fantastic. We knew that our array of the pill works. Let's take a second look at the visualization again. The visualization isn't all that telling because of all the rickerson that is happening, but it's interesting to watch and let's go. So we're assuming that the the primitive here is five, and those get switched into their larger or smaller this larger or smaller summaries also the quick sort of sometimes called the petition exchange sold, which I believe is a much more apt name for as actually partitioning and then sorting each of those different partitions. Oh, you understand the quick sort of tiny but better on old rhythms in fight in general. Thank you very much for joining me on. Have a fantastic date.