字幕表 動画を再生する 英語字幕をプリント (whistle toots) (laughs) - Hello! I should let you know I'm about to do a coding challenge, you're going to watch this, apparently, and I have been live streaming for three and a half hours (laughs) so my apologies in advance. But I'm excited to do this, I really wanted to try this for awhile, it's been a suggested many times. I am going to visualize a sorting algorithm and I'm going to start with the Bubble Sort, one of the most basic sorting algorithms of them all. And I might just do a follow up one with, like, a Selection Sort and then a Quicksort and other sorts, so suggest all your fancy sorting algorithms in the comments below (laughs). But this is inspired by many things but most notably, probably, this article called Visualizing Algorithms by Mike Bostock. This is actually an article from 2014, it has a wonderful set of interactive explanations of different algorithms, I'm going to search for sorting, and... Oh, that's the shuffling one, sorry. (laughs) I missed sources for sorting. Ah, right here! So this is visualizing the Quicksort algorithm. I like that what's happening in this I missed searching for sorting. so I think that there's a lot of really unique and interesting visual possibilities, that you could visualize data and then sort it and then visualize that sorting process. Maybe you could sort, like, musical notes or you could sort text, there's so many possibilities. So I encourage you to be creative with your own visual interpretation of what I'm going to do and share it with me. I'm going to do this in Processing, my happy place, thank you very much. I will make a Java script version of it, as well, with the p5js library so you can find the code for both of those things linked below. Okay, so let's just talk about what a Bubble Sort is first. I will make a JavaScript version of it, as well, with the p5.js library so you can find the code I talk about bubbles a lot, so this is kind of appropriate. So, let's say we have a list of numbers and list of numbers is in an array. So there is an array of one, two, three, four, five, six things and they're numbers like six, two, nine, seven, three, four. What a Bubble Sort does, is it starts by just comparing pairs of numbers. So, we start at the beginning and we compare these two numbers. And let's say I want the list to be from smallest to largest. I could want it from largest to smallest, or I could be comparing the values in any number of ways but if I want from smallest to largest, looking at these two values, I should switch them. So, what am I going to do? I'm going to have to draw this a lot. I swap them, I perform a swap. Two, six, nine, seven, three, four. Now, I look at these two values. Wait, this one's bigger than that one, I don't need to swap. Now I'm going to look at these two values, I do need to swap them. Seven, nine, three, four, two, six. Now, I look at these two values, nine is bigger. Two, six, seven, three, nine, four. Okay, now I look at the last two values, nine is bigger. Two, six, seven, three, four, nine. Now, look at this. The largest value is always going to end up in the last spot. So, I'm now done all the way up to the last spot, so I could do the same exact checking the pairs of values but just do them one at a time, all the way up to the last spot. So, this Bubble Sort is probably the least efficient sorting algorithm, in fact, it is an n-squared, Big O notation. Big O notation is about the order of an algorithm, how long does it take for an algorithm to perform, right? If I have six, an array of six things, I've got to do, how many slots? One, two, One, two, three, four, five. Then I have to do one, two, three, four. And then, one, two, three. So, as the array gets bigger, the amount of swaps I need to check grows exponentially. So, this is a slow algorithm but I don't care about that 'cause I want to visualize it. All right so, the next thing we're going to do is we need some way of visually representing the array. So I'm going to say void setup(), void draw(). I'm going to make an array, I'm going to make a window of size 600, 600. I'm going to set the background to zero. I am going to create an array of values, and that's going to be an array. I want to have the same number of values that I have as pixels, so I'll say width. And then I want each, I want to loop over that entire array. And I want to say values index i equals random height. So, I want to get a random number from zero to the height of the window because I'm going to visualize that. I'm going to visualize it now by saying for int i equals zero, i is less than values.length, i++. I'm going to draw a line from the bottom of the window, so, i, height to i, height minus values index i. So I'm going to draw a line with that random number and then, I am going to run it. Oh, maybe I need to set the stroke of the line to be 255 and there we go. So this is what I want to sort, this looks kind of weird. Let's it make it, I think I want to different aspect ratio. Let's make it like 800 by 500 or something. Okay, that's better. So this is what I want to sort, I want to sort all of these so we see the smallest one on the left and the largest one on the right. And I want to watch the sorting process happen in real time. All right, let's think about this. So, first let's program that sorting algorithm. Let's just do the sort right here. First of all, Processing, I'm pretty sure has built into it a function called sort. Ta-da! (laughs) I sorted it! (bell dings) Goodnight, thank you very much. (triumphant music) See you later. No, so I need to write the sort algorithm myself, so let's do that first. So the first thing I need to do is I need to have i equals zero, i is less than values.length, so I need to, what I'm going to do is for every single, for the amount of things in the array, I now need to check for int j equals zero, j is less than values.length minus i j++. Think about that. The first time I go through, I have to do every single swap. The second time I go through, I have to do every single swap up until one less, so then two less, then three less. So as i goes up I check fewer, I check i less elements in the array. All right, so now for each one of these things I'm going to check I'm going to get value a is values index j and value b is values index j+1. And then I'm going to say if a is great than b, then I need to swap a j and j + 1. So, this is a function that I intend to write, a function called swap which gets the values into indices and swaps the values in that array. I'm putting that in a separate function 'cause it's a very common algorithm to swap two values in an array and I might as well encapsulate that somewhere, encapsulate is probably the wrong word. I might as well farm that off to another function. Now, the thing is, I think this actually should go to minus i minus 1, because technically when I'm checking the last element I am checking the last element against the element before. The last element has no neighbor to its right so I actually should go minus 1 here. So then, I am going to write this swap function. I'm just going to put it at the bottom, swap. This is a generic function that gets any sort of array and an index, and an index i and an index j and what it does is, the idea, is what I want to say is index i equals the spot that j has and j, this is swapping the values, right? Maybe I should make these a and b, it might be a little bit more clear. A should get b's value and b should get a's value, right? That's swapping it. If you haven't seen this before, think about what's wrong here. What's wrong here? A should get b's value, b should get a's value. That's conceptually correct but guess what? If b gets a's value, a just got b's value, so b is getting b's value, ah! So, really what we need to do is temporarily store a's value, give a's b value, but don't worry we've saved a's value in temp, and now, this is actually swapping those two values. Okay, here we go. And now if I run this, haha, yes, so this sorted. So, great, I sorted everything with a Bubble Sort right up here in the top. But now I want to animate this. I want to just do one of these every frame, so now I need to think about the draw() loop. Based I need i and j to become global variables, right? The idea is here I want to do one of these each time through draw() I want to basically do this once and then I want the loops to just sort of happen somehow outside, like, I got to do those manually. So, I got to say int i starts at zero, j starts at zero, right? And so now, I do this first with i as zero and j as zero. Then, what? J goes up, j equals j+1. Now... Now, if j gets to the end, right? J's limit was values.length minus i minus 1. So if j is greater than or equal to values.length minus i, minus 1, then what happens? J goes back to zero and i equals i+1, right? So this is basically doing one step of the loop each time through draw(). J goes up always and when j gets to the end it goes back to zero and i goes up, and then j is going to go through all of that again. I think that's the right idea. Now, however, I do need an end condition, right, because at some point I only want to do this if i is less than values.length. As soon as i becomes values.length I want to stop doing this entirely and I do something like, it's finished, so I could say print line finished and I could say no loop. Dare I say that this challenge might actually be complete? I'll be shocked, oh my goodness.