(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)