- This video is sponsored by Brilliant. Hello and welcome to Coding Challenging, Quicksort visualization. What you are seeing here are
the results of my previous sorting visualization
challenge where I did the bubble sort. Now the bubble sort is
a really nice sorting algorithm to start with. It's pretty easy to,
relatively easy to implement with just some for loops,
but it's very inefficient. And it's super inefficient
because it is an algorithm that takes on average O, the
letter O here is standing for big O notation or
the order, the magnitude of how long a particular algorithm takes based on how many algorithms
of that element there are. So with an array of N elements, the bubble sort typically
takes ON squared. Now the Quicksort algorithm is on average a big O, N log N algorithm. Now maybe at the end
I'll come back to like unpack why is this. But one of the things I
love about the Quicksort is it's divide and conquer
approach that requires recursion. So I've done a lot of things
with recursion on this channel before, more in computer graphic or drawing a fractal
tree or some other type of recursive pattern, but
here we're going to see a recursive function, a
function that calls itself. So let me describe and
kind of diagram out the Quicksort algorithm as best
as I can before I start implementing the code. So first of all, let's
just say we have an array, and I'll just make a really
small array right now with just I don't know,
one, two, three, four, five elements, seven, two,
six, five, four, alright? So this is my array, and the
idea here is I'm going to write some function and I'm
going to call that function a Quicksort. Now this function is going to expect being passed into it some array, and then it also requires
the idea of the Quicksort is to say I want to apply
this algorithm the Quicksort, to some part of the array. And we're going to recursively subdivide and subdivide and subdivide the array and keep sorting different parts of it until the whole thing is sorted. It's like magic. But when we're starting,
what's going to get passed in is index zero and index four. So the first time I call
Quicksort I'm going to say sort the array from zero to four. Now one thing though that
I'm going to want to check, this is going to be a recursive algorithm, so the main thing is like
start has to be before end. So the array is going to
recursively get subdivided and subdivided, so at some point of start and end are in the same
spot, that's when I'm done. So that's going to be the first step here. If, I think I can just say
if start is greater than or equal to N, something like return. That's going to get me out of it. Alright, but here's the key. The idea of the Quicksort
is basically to say I want to do a step which
is called partition, and I need to pick some part of the array that is called a pivot point. So I'm going to make a
nice, a sort of easy way to pick that, it's always
just have the pivot be the end spot. Then the idea is I want to take everything that is less than the
pivot value and put it on one side of the array,
everything that is greater on the other side of the array. So if I were to do that with this, I could just visually see,
I'm going to get a two. Two is the only thing less than the four, and the four is going to go here, and then the other things are
going to be on the other side like seven, six, five. They don't have to be
sorted, seven, six, five. So this is what I'm doing. I'm taking this pivot,
putting it in essentially the center, the middle of the
array, and then everything that's less goes on one
side, everything that's more goes on the other side. So this partition function,
where I give it the array, the start, I think
I'll still give it the start and the end, and then
also the pivot, right? What I then want this
function to return is an index value. The index value of where
the pivot ended up. Actually I think I don't have to do this because I can always use
the pivot point as the end. So I'll figure that out as I code it, but stay with me here. So in this case, what this
actually ends up returning is the index one. Because what I then can
do is I could say hey, now that I got that index
of where that pivot is, I want to just Quicksort, so
I'm going to recursively call on that array from start
to that index minus one, and also Quicksort, this
is dividing and conquering from that array from
index plus one to end. So basically, these are the steps we get. We start with the array,
we pick an arbitrary pivot, we put everything on
one side or the other, and we figure out where
that pivot ended up, and we just Quicksort both sides, and those will put
something, 'cause this then, this is done, 'cause it
only has one element left, so start and end are in the same. So it'll return. This one will pick five as the pivot, and then it will become five, seven, six, because everything's on one side. Seven, six, are bigger than five, so this is then done. So this then gets Quicksorted,
six becomes the pivot, so seven goes on the
side and we're left with two, four, five, six, seven. So maybe my diagramming and
explaining isn't the greatest, and we also have to write
the partition function. I mean that's the whole, how
do we do this partitioning? But let's start, I think now
let's go over to the code and start writing in our code. So here I am with my code. I'm going to remove the bubble sort, and I'm just going to leave
the drawing of the array, and I'll take out this frameRate
five thing for right now, actually I'll leave that in there. And now if I go and refresh,
we should see there it is. Every time I refresh,
I'm looking at the array of random values, unsorted. So the first thing I
want to do is just see can I get the sorting to work, and then I'll figure out
visualizing is I guess the interesting part here in some ways, but let's get it to work first. So the idea, right, we
need to write a function called Quicksort. It's going to receive an
array, and a start and an end. And I said if start is
greater than or equal to end, then just return, like jump out of there. Otherwise, we need to get this pivot index where I'm going to partition the array from start to end. So I want to call this partition function. I mean this is really,
ironically I haven't explained the partition. That's really where the
algorithm is happening, but I want to run partition, and I definitely don't need
to pass in an extra argument, because I'm also going to use the endpoint as that pivot, so that's fine. And an index is going to come back. And then what I want to do
is say Quicksort that array from start to index minus one, and Quicksort, Quicksort that
array from index plus one to end. So this is the basic idea
of the recursive algorithm, divide and conquer, and I'm
going to call the array, I'm going to call it first
with values and go from zero to values.length. Now do I want to say
values.length minus one, probably. So I'll figure that out as we go, because the last element
is not the length, it's the length minus one. So okay, now of course,
so this is the idea. So now we have to figure out partition. Let's look at the partition function. This is really where the magic happens, this is the core algorithm. So once again, let's make
up an array with just five elements in it. Let's say nine, three, five, six, four. Let me move just to make things more even, let me put the four here
and make the five here. Okay, just to, I think an
example will work out better this way. Obviously any order the
sorting algorithm will work. So the idea of the partition function is when you call the function,
you give it the array, this is the array, you
give it a start and an end. So in this case the start
is going to be zero. This is the start. And the end is going
to be in position zero, one, two, three, four, in index four. So this is the first
time I call partition, it's going to get called on this array. Now what I need is the pivot value. I need a pivot index and a pivot value. The pivot index, well we'll
talk about that in a second. The pivot value, I could
pick anything in here, but it's most convenient
to just pick the last one. So I'm going to say the pivot equals five. And the idea of what I want
to do is I want to rearrange this array so that everything
that's less than five, like the three and the
four are on the left side, and everything that's greater than five like the nine and the six
are on the right side, and then five will be smack in the middle. Now it wouldn't always
work out that the pivot ends up in the middle, because everything could
be bigger and the pivot will end up here, and there'd
be nothing on the left side, but I made a little nice
example so that it works out cleanly. Okay, so how do we do this. So first we need to iterate
through every element of the array. I equals zero all the way
up to the end minus one. So we need to check every
single element of the array, and we need to compare every
single element of the array against five. I also need to keep
track of the pivot index. 'Cause as I go through this process, I'm going to need to find, once I'm done, the five is going to
stay here the whole time, I need to quickly put
five back in to where it's supposed to go. So that I'm just going to call index. It's really the pivot index. So this is the pivot value,
this is the pivot index. That's going to start at zero,
and I'm going to put a star here, for that it's starting here. So I is now zero. Nine, is nine greater than five. Yeah, it's greater than five, I know that. That means I do nothing. So I'm checking if array index I is, I'm checking if it's less
than, it's not less than. If it's less than the pivot value. So if it's not less than the pivot value, I don't do anything. Okay, now I goes up, so I is now here. Is three less than five, ah hah, it is. So guess what I did. I now swap I and wherever
the pivot index is. Remember the pivot index was at zero, so three and nine are going to swap. So three goes here and nine goes here. And then guess what I do? I move that pivot index. So the pivot index is
now here, and I move I and I'm checking four. Is four less than five? It is, so I do this again. Swap I and the pivot index. So four goes here, nine goes here, and the pivot index goes up,
so the pivot index is here. Then I go here for I, this is the last one I need to check. Is I less than five, nope, do nothing. So I'm done. This is the array, three,
four, nine, six, five. Well you can see that
three and four are here, they're less than five. Nine and six in here,
they're greater than five. Guess what? The reason why I need that pivot index, is the last thing that I do
is I swap the pivot index with end. So now I can just take
what was on the end, put it here, put the nine here, and I have, this algorithm
has successfully put everything less than that
pivot value on one side of the array, and everything
greater on the other side of the array. And the really nice thing
about this Quicksort algorithm is I don't really have
to use additional memory. I didn't have to make
a copy of the array to move things around, and merge sort, if I ever do the merge sort,
you'll see you need to start like having extra copies of the array. So that's one nice thing
about the Quicksort. So the chat is giving
me some good feedback. That the way I used I and
index is a little bit awkward. I think what I might actually
do is name this pivotValue, and when I write the code
I'll name this pivotIndex. That's being very long
winded but I think it'll make it more clear, so let's
go write that code now. So if I come back to the code, all I need to do is write
the partition function. So I'm going to write a
function called partition, it's going to receive an
array and a start and an end, and then what did I say I want to do? I need to have a pivotIndex,
which is going to start at zero, I need to have a
pivotValue which is going to be the array at end,
and then I need to iterate from I equals zero to I
is less than n minus one, I plus plus, and now I'm
checking if the array I, is less than the pivotValue. Then what I want to do is swap. I already have a swap function. A swap function just takes
an array and two incidents and says whatever was in A, store it, because you're going
to want to put B in A, and then what you saved in A, put it in B. So swap array A and swap array B. So I already have that function. So I can say swap I and pivotIndex, and then pivotIndex plus plus. And then once I finish that loop, I just need to swap pivotIndex and end. Array, pivotIndex and end. Wow, that was quick to write. Is there any chance that I got that right? Alright, let's run the code. Okay, we got an error. Maximum call stack size exceeded. So this is a very common error. Which is that if you
recursively call stuff way too much, things blow up
and you've exceeded things. So let's take a look at the code. Oh, of course, this is not
where the pivotIndex starts. Remember, I just said zero
because I was thinking about doing it over the whole array. But the whole point of
this is you're starting at start, start isn't always zero. That was a nice little mistake there. So this should be start. Is that the only error I have? Let's see, no. So there's some other errors, let's see. Oh, oh, yikes. I forgot, so I forgot
that my swap function, my swap function, the way that I wrote it, there's no global array. You have to tell it what
array you want to swap the values in, so that
needs to be explicitly added as an argument there. Was that the only mistake? Oh, oh you know what. Here's my other error. I know that this is, I
know that this is end, so I want my loop to go
from zero to end minus one. But I'm using just the less
than in my for statement, so I don't need end minus
one, I need just end. So many errors still. Oh, return the index value. Okay, I forgot the whole
central idea in this. The whole central idea of
this is that the partition function returns back
where that pivot index is so that you can divide and conquer and do the right and left halves. Look at this, I don't
return that anywhere. I just finish and I'm like I'm done, here's an undefined pivot index. I need to actually say return pivotIndex. What an important,
important key line of code. And, I'm getting closer everybody. And another mistake, oh
I made so many mistakes, I'm the worst. This is also from the start. I'm so focused on thinking
about the beginning first step where you go from the beginning
to the end of the array, but the whole idea of
this partition function is that you're anywhere in the array. So this goes also from start to end. There we go. So now there's my sorted array. You can see that the
Quicksort actually works. Alright, now that we're about
three hours into this video, I should visualize it. It's really tricky to visualize
something that's happening recursively, because it's
not happening in an obvious first step, second step, third step. So let me just draw it the first step, draw it the second step. So what happens, what do I mean here? What if I make this
Quicksort function async. Let's just add that async keyword there. Same deal, interesting. Let me also make this
partition function async, and what's important there, oh, I forgot. I forgot something really important. I'm surprised that even worked. If I'm making the
Quicksort function async, I'm going to await Quicksort
both calls to Quicksort. I want to be able, those
are happening asynchronously and I want to await them, 'cause I everything to
happen in the correct order. Also want my partition function
to happen asynchronously, so I'm going to put
await in front of that. Now if the async and await
key words are new to you, I will refer you to some other videos where I go through those in more detail. But this is what I'm basically
allowing this to happen is that this function
Quicksort can be called, and then draw is going to go on. The thing is the sorting is so fast, you can see it. There's like a little blip there, right? That little blip where you see it, but it sorts it so fast. What this means is if I could
just make something happen, let's make swap asynchronous, and let's await it everywhere. If I could just add a
little delay somewhere I could force the actual sorting algorithm to slow down but draw
would still be animating. Is there other places where swap happens? These, swap and swap. How do I make this slow down. Well I could use set timeout, but what I want is I want
a function that's like delay that I could use await. And I'm going to have to write
my own function for doing that. So on Stack Overflow, I
found this nice piece of code that basically takes set time out, the set time JavaScript
function, which has a callback, which is callback based,
and resolves a promise when set timeout finishes, and this is the equivalent
of an asynchronous sleep function. It's kind of like await
and don't do anything. Wait and don't do anything
for this amount of time. So I'm going to bring this
function into my code. I'm just going to put
it here on the bottom. And now I can say await, sleep, 1000. What that means is hey, before you swap, just wait a full second. And let's see what happens. I think my sleeping might be too long, right, a full second. So let's just bring that down to ten, and we could see, there we go. So one thing that I
noticed and that the chat really just helped me out with, is that because I am
using await here with each separate Quicksort step, the actual sorting visualization is, the recursion is not
happening simultaneously. It's doing one half then the other half, then one half then one half
then one, step by step. Which is kind of nice for visualizing, and that's really really fast. I'm going to put a sleep
time of like 25 milliseconds. And you can sort of see
how this is happening little bit by bit by
bit, and then it's done. However, I forgot that
I could use promise.all. So I could await promise.all. Both of these calls to
Quicksort at the same time. So if I do that, just
paste this one up here. This is getting to be pretty goofy advanced JavaScript stuff, but this is basically
saying hey, you could go do both of these simultaneously, I'm just going to wait for
both of them to finish. And this in theory, can you
visually see the difference of that? I don't know how obvious that is to you. It'll be much more obvious
if I did something like color the various pivot points. Let's see if I can do that. I have a really goofy
idea of how to do that, which I think is probably terrible, but this is the last thing
I'm going to do before putting this aside. So what if I have an array, 'cause there's multiple pivot
points that are being tracked. What if I have an array called pivots? And anytime, should I draw
the pivots as they're moving? Or just draw them, let me
draw them as they're moving. I'm going to do overkill. This might not be the classic
way of visualizing this, but basically whenever
I get a pivot index, I want to add it to this array. I really want to use
just like a lookup table. Actually that's what I should use. Ah hah, so what I want is an array. 'Cause I really want an
array of true and false. What's the state? Let me do this, this is much better. States, so as I'm creating my values, the states of every single spot
is going to be negative one. So what the current status
of a particular element of the array is is how
I choose to color it. So in the case of whenever
I get a pivotIndex, I'm going to say pivot,
I'm going to say states, pivotIndex equals zero. So negative one means nothing,
zero means it's a pivotIndex. So this is a little bit
ridiculous, but let me just, bear with me, and now I'm going to say if, if states index equals zero, which I meant for pivotIndex,
fill, make it red. Otherwise, otherwise make it white. This is going to be good. I think this is going
to get us what we want. So you can see anytime
there's a pivotIndex, it's set it to red. Now I'm not unsetting it. So one thing that I could
do then now is I could say here if I'm moving the pivotIndex, right before I move it, let's
set that back to negative one, and then set it again to zero. So now you can see the
pivotIndexes are moving. Now again, I'm not
unsetting it when it's done, which is sort of a problem. So I suppose if I wanted to do that, I could also say states index, this is worth like finished. There you go, so it's
happening very very fast, but that's the pivot stuff moving around. I don't again, I don't know if
I'm doing this the right way, but it also might be
interesting to as I'm sorting between start and end, any
given active partition. Like I could do I equals start, I less than end, I plus plus. I could say states index
I equals two, or one. And I could also at
the end after I'm done, set it back to negative one. So I could say that if,
else if states index I, equals one, then maybe make it blue. Again I'm not really too
thoughtful about my color schemes, but let's see what happens here. I don't know, that's kind
of like what's going on. Let's give ourselves a much
bigger space to work with. Let's actually make this the full window. Window height. Let's make the width
of each one just five, and then I think I probably
want to say no stroke here. 'Cause if they're thinner that
might mess up how it looks, and let's make a hundred
milliseconds sleep time between each swap. Let's go enter full screen and
I'm going to let you enjoy this, I'm going to step aside. (upbeat music) Alright, I need to change the
colors, those were no good. Oh, so and oh, there's another mistake. If I don't want to, if I is pivotIndex, so as long as if I is
not equal to pivotIndex, I don't want to undo, I don't
want to undo the coloring of it being currently sorted. Alright thank you to the
chat who offered these colors as suggestions. I'm going to just leave it at that. I'm going to make the
lines a little thicker. Let's leave the width at ten. Let's make it run a little bit faster. So I'm going to double the speed. Alright, I've got the code
in the state that I want. I'm going to play you out,
and let you enjoy this last visualization of the Quicksort, and please make a nicer version of this, add sound, add better colors,
do all sorts of stuff. Here I'm going to hit refresh. (bell dings) Thank you for watching
this coding challenge, visualizing the Quicksort algorithm. You might notice that
the version that I made looks okay, I did fine. It might look different then some others that you've seen in particular,
there's a very popular video on YouTube called
15 sorting algorithms in six minutes, it has
like six million views as of the time of this recording, and the Quicksort visualization
looks kind of different. And that's because there
are actually multiple ways to do that partition step, that partition function,
that takes the values of the array and puts
a bunch that are bigger on one side and a bunch that
are smaller on the other side, and there are two techniques. There's the Lomuto partition scheme, which is attributed to Nico Lomuto, and that is the one that
I'm using where you pick that pivot and then you
start at the beginning of the array to check
everything and figure out where that pivot should go basically, where it should get moved to. There's another one called
the Hoare partition scheme which is described by C.A.R. Hoare, you can find more about
this on the Quicksort Wikipedia page, that
starts with index size at both ends of the array
and has the walk towards the middle swapping elements. And that's in a way, that's
one that you should try. So if you want to go look that up, look that algorithm up
and try changing my code but still visualizing it,
that might be something exciting to try. And maybe you have other
ideas for your own version, for your way of visualizing
this Quicksort algorithm using color, using sound,
using shapes and design in a different way. You don't have to be sort
literal about the array as just a bunch of bars going horizontally across the canvas. Please share with me your
version of the codingtrain.com, and I'll put a link in
this video's description. And there you'll find pages for
all of my coding challenges. Now one of the things that I
really struggle with these days is how do I think of a
new idea for next week's coding challenge, and I get
a lot of great suggestions from the audience. I get ideas from my students here at NYU, but I'm excited to tell you
about the sponsor of this video, where I is a treasure trove for more ideas for coding challenges,
and that's Brilliant.org. Brilliant has a wide range of content, math, and science, and computer science. They have daily puzzles,
they have courses, I've actually been enjoying
looking at their daily puzzles and trying to
solve them with JavaScript, and that's been a sort of
fun way for me to try to learn something new and also
practice a little more coding. And in fact, probably most
relevant would be the courses on Brilliant that are
computer science fundamentals. Intro to algorithm, recursion, you'll see lots of things
from my coding challenges in that course as well as the
computer science algorithms course where in fact there's
a whole module on sorting, and I reviewed that
Quicksort, the Quicksort while preparing to do
this coding challenging. To sign up, go to
Brilliant.org/codingtrain. That will let them know that
you found it from this video, and also as a special offer
to Coding Train viewers, the first 200 people to
do that get 20% off their premium service. Thanks for watching, I
hope to see you in future coding challenges, and I
can't wait to see what kind of Quicksort visualizations you make. (upbeat music)
