## Subtitles section Play video

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

• 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,

• 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.

• 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++.

• 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