(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. Shortest challenge ever, I love it. Oh no no no no, no no no no, no. (buzzer sounds) Oh, whoops! I think I did everything correctly but I just put this inside here. The whole point is do
that and when you're done, then say println() finished
and noLoop(), right? Do all this stuff, the
incrementing through the sorting and then when I am done, say that. Okay, okay, okay. (exhales loudly) Breathe everybody, let's breathe. Here we go, here we go. Oh, it's sorting, look! Look at that one line
just traveling across, hi over there! Oh boy, this is going to
take a really long time. (laughs) How much time do you have? (cheesy elevator music) Okay, never mind, never mind. I did some calculations and that was going to take about
an hour and 10, 20 minutes, hour and a half, something
like that to complete. So we're going to, number one,
is going to be like, oh, I know, let's just do a little
tiny 100 by 100 window. Oh, maybe we could sit here
and actually watch this sort. So, I do kind of like the
idea that I'm seeing that, sort of like, line going over time. But... yeah, I'm going to need
to speed things up. So, let's do that. Let's go back, let's not be as ambitious. Let's do 400 by 300 and
then I'm going to do this, I'm going to do this. I mean, I could do the full j each time but then it's really
like a Selection Sort, which is, I don't want to do. So, I'm going to (laughs) this is a flawed idea. I'm just going to do like 100 per frame. So I'm going to add, oh, can't add. I'm going to call this n. I'm going to just do
this 100 times per frame. You know what, the print line is something I really
should take out here. I should basically, I'm
making this a Selection Sort. By the way, spoiler alert, the next video I was going to make I'm now basically making now. A Selection Sort is, instead of swapping, bubbling through the whole array, you just look through the whole
array, find the biggest one, put it at the end. And look through it again,
find the biggest one and put it through the end. So, I would have to write a
slightly different algorithm to do that, but in essence,
I'm going to animate this as a Selection Sort by... going here and just saying just having i go up by 1. So, every frame I'm going to say for, I'm going to take this, and I'm just going to do all the js. Oh, wait a second. No, no, no no no no, no no no no, no. I made a big mistake here. If I'm going to do it more than once, I got to swap each time, too. (laughs) So this should really, I don't know why I have this here. This should have all along, boy, now I suddenly
made this a long video, 'cause of my incompetence. I should have had this
all along, basically, well, I like the idea of
doing it first, but... in here, so hold on. Bear with me for a second. I'm going to leave this up here, I'm going to take this here, I'm going to do one i each time then for every j I'm going to check the values so I'm still doing the Bubble
Sort but I'm only going to update and then, every frame I'm just going to say i++ and then I have some extra brackets here that are totally unnecessary. All right, this should now visualize a little bit faster. Oh, that's kind of nice. (laughs) There we go. (smacking kiss) Now, let's make it bigger. Let's make it full screen. Come on, everyone. So, this is my basic sorting algorithm that is doing a Bubble Sort
but I'm only visualizing every way all the way through, so really, in the end it's kind of like a
Selection Sort visualization. You should do something
like sort by color, sort by frequency of audio, sort by text, something else, and in fact, what if I use perlin
noise or like a sine wave? What if I said... noise of i divided by 100, this is using perlin noise, times height, this should
be kind of interesting. Whoa, oh, that's weird. Oh, 'cause I used integers. Ah, because I didn't say point zero, that's kind of cool. Let me do this. This is what I meant to do. Yeah, look at this. So I had like this mountainous
region that I'm now kind of like sorting, this
is actually kind of cool. Oh, this is more than
just a Selection Sort because the other stuff is
swapping, as well, I think. It's confusing to think, it's hard for me to think about this. Anyway, you get the point. (laughs) There are lots of possibilities here. Make your own beautiful version of this. Think about the algorithm
in a different way, think about the data you're
sorting in a different way, put this one the web, share it with me. Sorting train, #SortingTrain, on Twitter #SortingTrain,
there'll be a link to thecodingtrain.com webpage where you also can submit contributions and I look forward to
seeing what you make, okay? Thanks for watching!
(bell dings) (groovy upbeat music) (bell dings)
I think I'm going mad. I swear I saw this video on YouTube like a week ago and even followed along.
Was it re-uploaded or something?