Programming BASIC and Sorting - Computerphile

Key Takeaways

so each time it swaps a pair of elements it plays a sound of both of them which is you can you can hear the sort of fluctuating pictures each time it Compares it each pair of elements it plays a noise and then potentially swaps them um what we thought we'd do is make them all sort 100 elements and you see them side by side in the last couple of videos we've done on sorting algorithms there's been quite a few comments uh on the videos and requests from people to do uh some more on different sorting so it's been a couple of weeks since we did the videos and um also there's been some more videos on computer file in particular I saw the one on the BBC micro so the BBC wanted to develop a project to introduce people to computers and uh programming they commissioned a British company called Acorn to make this computer and how easy it is to use basic to draw things on the screen and make noises this is an a5000 which is a computer made Acorn which dates from about 1991 I think so um it's it's kind of a descendant of the BBC micro it's it's got an arm chip uh which the BBC micro didn't have because it's uh an acorn it's got um it's got BBC basic interpreter built into it there is a BBC basic interpreter for Windows uh it's a bit Limited in terms of what you can use for memory and I didn't want to have to pay for it and I have this sitting in the corner like the BBC micro the operating system is in ROM so turn it on and it's it's pretty quick to boot up so we just wait and there we go it's booted up unlike the BBC micro this boots up into a gooey you've got a mouse and some things to click on this is called the icon bar at the bottom here and this is a hard drive icon so you click on that it opens the contents of the hard drive in a window that look familiar to you probably if you used any B operating system this is the floppy drive here so you click on that it'll say Drive empty it is and then we've got apps which are some built-in applications and networking and over here we've got graphics options and operating system options so acon we're talking about apps back in the '90s well yeah it's just short for applications so if you click on it you've got some built in basic things so you've got an alarm which tells you the time if you click on configure brings up the configuration so you can change things like sound options so I can change the noise to be various different things when I was looking at sorting algorithms on YouTube I found another video or another couple of videos made by someone else who had written a program in C++ that did visualization of sorting algorithms so it would um show you an unsorted list and it would sort into Order each time it would swap a pair of elements or do something it would play a certain pitch depending on the value of that element well that's quite interesting but there are some sorting algorithms that they haven't done that I'd like to see so I thought I'd do it myself they posted their source code and it was using some C++ library that I couldn't get an update version of on my system so a library is just a collection of of code written by other people that does a certain task for you so you can just use that most people use libraries of code because you can generally be guaranteed that it does what it's supposed to do correctly and I thought well having seen that BBC basic video um the the the triangles program on screen I can show you you know I did my own implementation as well as play the triangle on screen I also decided to make it make a noise so if I can show you the source code for that this is it I'm going to put some spaces in just make it a little bit clearer mode 27 tells it what screen resolution to use and what colors available that sort of thing okay and then we've got this repeat until false block what it does it repeats all this until false and now false never evaluates to true so it just repeats it forever this says set a variable called color to random numbers between 0 and 7even this then says set the graphics color to that random number between 0 and 7even then we play a sound related to that random number as well so the numberers between 0 and seven we need to scale it to be in the range 0 to 255 that's the pitch value and it zero is the lowest pitch it does and 255 is the highest pitch it will do if we left it 0 to 7even it would just be very low and they'd all sound quite similar this line that says plot actually draws a triangle so that's what you would have seen in the other video now this line is here to slow it down because it goes very fast on this so if I comment this line out we use REM which I think stands for a reminder so if I save that and then I run triangles again it goes so fast that you can't hear any sound because as soon as it starts playing one sound it tries to stop playing the next and you can't hear anything another thing I used was um a book that came into my possession or came into the office called games for your BBC micro this is just code listings of of certain games the first one I did was quite short it's called Dr audio it says this game is a variation of Dr Watson in which when you guess the computer's number the feedback is given as a tone the pitch of this note varies according to how far your guess is from the correct number the sounds are programmed in line 130 this is where how I learned how to do sounds because it said line 130 sound 1 minus 15 ABS a minus B 5 so it turns out that I had to look this up because it wasn't in this book sounds takes one two three four different uh parameters so the first one is the channel you want to play on uh I think Channel Zero does percussion sounds or something strange so anyway the first argument says play it on channel one the second one is the volume and that has to be between I think 0 and minus 15 minus 15 is the loudest Zer is the quietest this says ABS a minus B so that subtracts one number from the other and um gets you the absolute value of it and then the last one one is the duration of the note it's in CC so it's 5 hundredths of a second it plays it for here goes the program it might have rude words in it I can't remember so I thinking between one and 100 what is it let's go for 25 okay it was changed a little bit from what you said in the book but I wrote it so the higher the pitch is the closer it is 25 is wrong you so what's my next guess I'm going to say um 75 so 75 sounds closer let's try 80 no that's that's further away UH 60 yeah I'm going to go for 70 hooray where was the disc then with that book where's the disc the disc is uh the data is stored on the pages which means you've got to transfer it via your hand and the keyboard so show me what that meant okay so what I had to do is um type everything in to a nice text editor this one is not particularly nice this is the code that does SL program this is about 30 lines probably now I kind of was a little bit more familiar with BBC basic and how to draw things in certain colors and how to play sounds I decided that I could probably implement those visual sorting programs so first of all we've got bubble sort I think this sorts uh 30 elements so with bubble sort We compare elements and keep swapping elements if they're bigger than the ones in front of till they get to the end so um the green elements are ones that are in the right place red elements are unsorted and the blue ones are sort of ones that are being ones that are active at the moment so for 30 elements that took 23. 38 seconds 384 comparisons and 228 swaps so if we change it to 60 elements open it in the editor and change Max file from 30 to to 60 so save that okay so now we've got six0 elements we've doubled the input size and because it runs with the square of the input size 2 * 2 is four so it should take four times as long with four times the number of comparisons and four times the number of swaps each time it does a comparison and each time it does a swap it it increments a counter and just prints it out up here so each time it swaps a pair of elements it plays a sound of both of them which is you can you can hear the sort of fluctuating pitches each time it Compares it each pair of elements it plays a noise and then potentially swaps them it's getting smaller now we're only exulting say 20 maybe now what this is showing uh us is each of these columns which is the same width is a different number and so that's a low number and this end you've got a high number so when we start out the list is unsorted so you've got sort of Al high and low columns all next to each other and and when we have sorted the list and it with low numbers at that end and high numbers at that end we also covered quick sort in our previous videos so show you that so there's a variable called number of elements that's set to a thousand so I'm going to reduce it to say uh 400 okay and we've also got another option here so we can set graphical to true or false actually what you find is if you really want to do proper speed tests you need to turn the graphics off because they slow it down a lot if you want to prove a point and uh do something like this by the way this graph is link to from the previous sorting videos so let's save that and then run it so we've got quick sort so here's our list of unsourced elements so you can see there's all sort of high low ones hopefully you'll remember from the video on quick sort the way this works it partitions the list by picking an element called a pivot and putting all all elements Less on it on one side and greater than on the other side and then it then it does that again on each sub on each side so you can see it's kind of it's all the left hand side and now it will start doing the right hand side so there's the pivot it does all the left hand side picks another pivot keeps doing that until it's sorted you can see with quick sort it is a lot quicker than bubble sort another algorithm that we didn't cover before but is still fairly simple is called selection sort you go through your list and you look for the lowest element that's in the in the unsorted list and you take that and you put it in your sorted list you go through the unsorted list pick the lowest element from there put that in your sorted list here's 100 elements being selection sorted we got to look through the whole list find the small list and then we put it at the other end so is this a quick one this is not particularly quick this also is N squared because you've got to look at to look at these over and over again it's the same time complexity as bubble sort although I think it might perform a little bit better because it does slightly fewer comparisons well it certainly does fewer swaps it only needs to do at most one swap per element in the list whereas bubbles can go crazy the comparisons are still quite high and that makes it a little bit slow and what we thought we'd do is make them all sort 100 elements and um you can see them side by side and hopefully uh sped up a bit because some of them are quite slow [Music] [Music] what we've seen is bubble salort and cocktail sord and selection sort are quite slow in comparison to quick sort um quick sort runs in N log n um as we said in the quick sort video uh another algorithm that people were asking about in the comments is Heap Sort that also runs an nlogn you need quite a lot of background knowledge to understand how it works so Heap Sort uses something called a heap now a heap is a type of data structure which is represented by a binary tree whereby every element in the tree um has children who were smaller than it we haven't covered trees to cover trees we need to probably cover link lists to cover link lists we need to do something about data structures and we haven't got there yet however I will show you Heap Sort before I start it what it does it builds a heap up the largest element is always at zero and then it swaps that element to the the end and it restructures the Heap so that the largest elements again at that end well let's let's go so this is building up the Heap now it's built the Heap it can keep taking the largest element and maintaining the Heap [Music] structure and producing a sorted [Music] list that was quite quick that was 100 elements so it's the same as the other ones we've just seen if you know what Heap is and not it's that's different from the Heap the Heap is um an area of memory as opposed to the stack but the Heap and a heap not the same thing ethernet is not concerned with the internet as a whole it's not concerned with getting something we can we and then we say which is lowest between seven and eight it's seven uh which is lowest between eight and nothing it's eight and then similarly 10 and nothing it's 10 it's the idea that we've got it in the case of ipv4