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