Placeholder Image

字幕表 動画を再生する

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