midterms 2
Any questions?
So you know, and also for the record, like I know the late policy in the class is like you have to beforehand.
If it's five minutes beforehand and you're like, this week has been an absolute shit show.
Can I come talk to you tomorrow?
Yeah, great, come talk to me.
Like we can do that.
It doesn't, you know, like I said, I'd much rather have someone just grown up to be like, I don't know what the fuck happened but like I still, I don't understand this.
Can we talk?
Yeah, yeah, we can, 100%.
Okay, so that's just your mid semester reminder.
Okay, so we've got that.
And I told you about the midterm check in, the project check in.
So there's no specific lab this week.
I mean there's the, the lab this week is, you know, not a new one.
It's the midterm project.
So if you've already finished, I don't know, I'll figure something out.
And yeah, so we've got that.
So today we're talking about.
So last, not last week, the week before last we talked about searches, right?
Linear search on an unsorted list, binary and or AKA dictionary search on a sorted list.
Dictionary search obviously way faster, way more efficient, like way easier to get in there and find out if the thing you're looking for is in the list or not.
Far fewer things to look at.
Small problem list has to be sorted.
So then the question becomes like, oh, okay, how do we sort the list though?
And yes, there is a built in Python function that will sort the list for you.
There's more than one actually.
But you know, being able to like think your way through sorting the list as it turns out is super important.
So today we are going to do that.
So.
Or for the next two weeks actually because it turns out there's a lot of serving algorithms.
People have a piece of means.
Got sorting algorithms more did I use out of pocket, right?
I think so.
My, one of my goals is to just constantly keep using new stuff lang terms until it's just like I'm going to be like 87 and whatever this line is going to be when I'm 87, be like right there, like, yep, of course I then just continue to also say things that haven't been cool in a very, very long time.
I don't think anyone says cool beans anymore, but they should.
I like that.
Yeah.
Okay.
All right.
What about old hat though?
Good one.
Okay, so when I was in high school I said something was either cool Beans or old hat.
It's like an old hat, like something we used to do.
I like that too.
That's good.
Okay, so when it comes to sorting algorithms, there's a few concepts that I'm switching this up a little bit.
I'm going to try to introduce these concepts first so we can keep them in mind as we are learning about how these, all these different sorting algorithms work.
So the first thing obviously that we want you to think about is speed.
Slash, right?
The big O time.
We want to make sure that we're not using a sorting algorithm and it's going to be absolutely ridiculously slow.
I cannot remember, did I tell you all about bogo sort?
Okay, so the kind of classic example of the stupidest possible sort is what's referred to as the bogo sort, because it's sort for bogus sort.
And the idea is, let me actually also, I don't know if you all know that you can do this.
Like at any point you can open up a terminal or a command line and just go in and type in Python if you're on Windows, or Python 3 if you are on math or Linux and is that big enough?
And just start doing some like, Python typing.
So for example, I can say L equals, I don't know, random list.
Do I remember how to shuffle the list?
Apparently my U key has decided to stop working.
Bogo sort is the idea that instead of like taking any kind of logical way of sorting a list, we're just going to go in and shuffle the list and check does see if it's sorted and if it's not sorted, we shuffle it again and then check to see if it's sorted.
Oh, almost.
Well, not almost, but hey, zero is in the right place.
But it's not fully sorted.
So instead of being like, okay, maybe we'll just shuffle the rest of the list.
No, we just start over.
The Wikipedia page has some like, interesting arguments about this in the comments section.
But right now it is estimated that a bogo stored on this particularly large list, which you think will be heaped out of the universe.
So obviously, bad sort, not good.
Like we don't like that.
So we're not going to implement that obviously.
I mean we'll be.
But I basically just throw this in the for loop and then check to see if the list was sorted.
Terrible idea.
We can do better.
So obviously, yes, when it comes to these sorting algorithms, we do care about speed and efficiency, but we do have a small problem which is that like, if you are sorting a list, there is a very hard limit on how fast you can actually sort it because you have to go through the whole list multiple times.
So the trick is going to be okay, but what's the fewest possible times that we can go through the list?
But also the other things we want to think about, so speed, efficiency.
Well, we also care about what's referred to as stability.
So stability means if two elements have the same value to keep their relative positions is stable.
So for example, do I have my other markers?
So for example, let's say you started off with this list and got a 10, a 2, an 8, a 4, another 2 and a 7.
There's an odd number in there.
So in a stable sort, what will happen is that these twos will maintain their relative position.
So the two in blue will come first, then the two in green and then the rest of the numbers.
An unstable sort would swap them.
The green two and then the blue two and then the rest of the numbers.
So it's not unstable in the sense that like you can't trust to sort the list.
Like the list is still sorted.
But you know, when we first started this two came first and then the other one.
So why would that matter?
Like who cares if one two is for another two?
Aaron, would it matter like if you were to be sorting like say like keys in like a dictionary or something?
Like if they held different values?
Yes.
Right.
Because what we sort things by might not be the full representation of that object, right?
Oh no, just essentially that.
Yeah, yeah, right.
Because like we might sort people by.
I'm trying to think like what's a non unique way that we might speak.
People we age.
Yeah, we might sort people by age but you know, it still might be that, like.
Well, okay, you know, yeah, we're sorting by age but yeah, I still got here first.
Right, like.
Or if you're sorting people at the airport by priority.
Right.
Some people have priority boarding or like they're in their.
Of course airports don't actually do this in my experience.
But you know, you're at the gate and you're waiting.
Wouldn't it be kind of nice if you got there early?
And that meant that like in your boarding group you got to go on first if you wanted to.
Right, like so that the order of arrival was maintained even after like kind of sifting people out into their different groups.
That might be nice.
So yeah there's.
So yeah, stability can be really useful now again, depending on what you're sorting, you might not care.
Like stability might not be important for your particular implementation, but it's good to know about it so that you can choose to do it or not do it if you need to.
All right, next concept to keep in mind is adapty.
So that is whether the sorting algorithm can tell if the list is sorted, stop if it is.
All right, so a sorting algorithm is adaptable if the algorithm itself can tell if the list is sorted and then stop.
So you could be going through a list and, you know, moving some stuff around and then the algorithm goes, hey, I think we're done, we don't need to keep, we can stop now.
Most sorting algorithms in their base forms are not adaptable.
Some of them can be made adaptable, some can't be.
So this could be really useful if you are like, you know, I'm taking in all this data, most of it's going to be sorted most of the time.
So I don't want to waste a lot of time going through everything and checking over and over and over again.
So, you know, maybe I'll take a hit on speed because I know that like 97% of the time it's going to check the list once and go, now we're good, right?
That could be a valuable handoff.
Making the algorithm adaptable won't change the big O time of the algorithm, right?
Because worst case cases, the list is incredibly not sorted or horrifically not sorted.
But in like day to day, if you're like, yeah, okay, but most of the time it's going to be fine.
I just need to check occasionally.
That can be really useful.
And then finally, memory.
So the question here is how much extra space does the algorithm take up?
By which I mean, is most of the sorting kind of like you have your array and you're kind of just swapping numbers around, or are you making an entire extra copy of the whole array and like moving items into it?
Right.
Sometimes it can be really fast.
Actually, we'll see not this week, but next week that there's a sorting algorithm that can go much, much faster, Guaranteed every time.
Not all of them can guarantee, except that sad story, it requires twice as much memory.
So like, whoops, another trade off.
The constant theme of this class is constant trade offs.
So but if you have the space, like if you know that your computer has enough extra memory or whatever device you're using, it can fit this, then great.
Doing the sort that's guaranteed to be faster can be fine.
So just that's another thing to keep an eye on.
How much space does it take up?
And we actually do Talk about this.
An algorithm that creates an entire extra copy of the list to be sorted would be said to use O of N memory.
Right.
Because it's.
We're not talking about speed in terms of like the number of things they have to do, but in terms of the amount of space something takes up and seeing full of any space.
So like so much to think about, so complicated.
But we have reached one of my favorite parts of this class.
I hope the volume is loud enough and not too loud.
So basically two things here.
First of all, so this is a.
The quality of this video is absolutely terrible because it's so old.
You'll notice that this is from 17 years ago.
This is Barack Obama before he was president, being interviewed by I think the CEO of Google.
And well that's now Senator, you're here at Google.
And I like to think of the presidency as a job interview.
Now it's hard to get a job as president and you're going through the rigorous.
Now it's also hard to get a job at Google.
We have questions and we ask our candidates questions.
And this one is from Larry Schwimmer.
What you guys think?
I'm kidding.
It's right here.
What is the most efficient way to sort a million 32 bit integers?
Well, maybe, I'm sorry, maybe I think the bubble sort would be the wrong way to go.
The bubble sort would be the wrong way to go.
That is an actual sort.
He is 100% right.
The bubble sort is the wrong way.
But that's the first order that I'm going to teach you.
So when I say that at job interviews you are going to be asked about the things you learn in this class.
Even Barack Obama.
Okay, I didn't see computer science.
We've got our spies there.
What does that mean?
What does that say?
That was excited.
I, to this day I've never seen an explanation.
To be fair, I haven't like done a deep dive, but I've never seen an explanation for why he knew that.
Never seen one.
Who this degree in.
Wasn't he like a lawyer?
Yeah, but I don't know what his undergrad degree, which is not computer science though.
So yeah.
Okay, so we have a few different sources we can use.
And as Barack Obama correctly said, bubble sort is in fact not the most efficient sorting out there.
It's not necessarily the right way to go.
But the beauty of bubble sort is that it is simple.
So I'm going to teach that to you first because if nothing else, at least now you can like show Your friends this clip and be smart that they don't make the joke.
So I should not have erased that example array.
I'm going to need it.
Whatever.
Can I erase this?
I'll pull something else up and so if you need to copy this down, do it now.
Bubble sort.
That is truly what it's called.
For the record, you did not get wrong.
So rather than walking through it first, I just want to show you the code.
This is the entirety of the code for bubble sort.
This is in terms of sorting algorithms, as simple as you can get and still have it finished.
Like obviously shuffling and then checking to see if it's sorted is simple, but we are not going to do that.
But so we can see here that we've got a list.
That was a good one.
4, 2, 7.
All right, so we have, we're sorting a list for range for I and range the length of the list minus 1 to 0, negative 1, that crap.
Does that mean.
Yeah.
So can I ask why you're using command prompt instead of VS code?
Yes, and I'm glad you did, basically because right now the only thing that I want to do is just really quick stuff.
I'm not going to take out the full code and run it.
So I just wanted to do it this way.
And also because I wanted you to see that this is an option.
Okay, so for I in range from the length of the list to zero, negative one, we're going to go backwards.
That's all that means.
So we're going to start.
So this, the outer loop is counting backwards.
I really like this.
Textbook.
This is a good book.
And then for J in range I.
Okay, well if I is going to start at 6, then J is going to go from whatever that is.
So for this list, if we were to do a bubble sort here, we're going to go from zero.
So the outer range is going to be zero to four.
Well, sorry, just getting.
It's going to be four, zero and J.
So when I equals.
I'm sorry, the length is 6, not 6 is 6.
It'll be 5, 4, 3, 2, 1.
The time change is killing me.
And also for some reason my cat does not sleep in an hour.
I was like, oh, at least with the time change she won't get up at 6:30 anymore.
She's 7:30.
No, somehow she's still getting up at 6:30.
How?
I think she can read clocks and that is both very cool and very upsetting.
So, yeah, I am a little sleep deprived more than I should be at the end of break.
Okay.
So If I equals five and we start off with first loop, J equals zero.
I'm saying if a list J0 is greater than a list J plus one.
Okay.
Now if J plus one equals one.
So we're looking at these two values and we're saying if the one at position zero is greater than the one at position one, what do those three lines do?
5, 6, and 7.
What's happening there?
Yeah, we're just swapping them.
Right.
So it's going to create a temp value 10.
All right, so temp is going to be 10.
And then we're going to take whatever's in J+1 and move that over and then we'll put what we put in the temp value there.
Okay, that's it.
That's the whole first inner loop.
So we go back around, J gets incremented to one, and we do the same comparison.
Right.
So now we're looking.
We've moved up.
Now we're looking at positions one and two.
Is 10 greater than 8?
Yes, it's is.
So we swap them, go around again.
J equals 2.
Now, so we're going to compare 2 and 3.
Is 10 greater than 4?
It sure is.
Those get swapped and we just keep doing that.
So j equals 3.
So we look at 3 and 4.
10 is greater than 2.
J equals 4.
We look at 4 and 5, 10 is greater than 7.
J equals 5.
So we stop because we're out of the loop.
And we finished one go through of the inner loop.
The reason that this is called bubble sort is because every pass through this inner loop, the next largest item in the loop has bubbled to the top.
Yeah, I know, right?
It's so literal and also.
So, like, not literal, but yeah.
So bubble sort is going to go through.
So after the first iteration, it just so happens that I put 10 in the first spot here, that I put the largest number in position zero.
That will not always happen.
Obviously, though, in this particular case, the next largest number eight is like.
Yeah, well, okay.
Yeah.
So, yeah, so bubble sort, every pass through, every iteration through the inner loop equals next largest unsorted, or more political way to say it, largest number bubbles.
Sorry, could you please go over again how you are like marking the values on the list like the values of.
So I'm crossing out numbers as they get changed.
Right.
So the first time, like the first go around through the list, we had 10, 2, 8, 4, 2 and 7.
Right.
So as we're going through that inner loop, we're going to compare the basic position to 0 and 1.
Right.
And 10 is bigger than 2.
So we're going to swap them.
So I'm just marking that by like crossing out the previous values and writing in the new values about them.
Yeah, just so you can see how it's changed, that's all.
Yeah, Joey, maybe weird question, but why does it need to count backwards?
No, it's not a weird question at all.
It's a great question.
So in theory, it doesn't like.
Honestly, it doesn't actually save a whole lot of time, but.
So we've just gone through one iteration of the list.
Right.
So now that we've done so, after first task, we have two eight, four, two seven.
Right.
So the one thing, we're now in our second outer loop and we have to go through the inner loop again.
10 at this point is correctly post.
Right.
10 is the largest number in the list.
It's at the end of the list.
We don't need to look at it again.
So by having the outer loop count backwards, so this time this go around through the outer loop, I equals four, which means that J will never get to be larger than three.
So the outer loop is just set up so that as we correctly place numbers, we don't have to look at like that last position again, let me walk through the second for seriation.
Just do it that way.
Okay, so we're starting off I equals 4, J equals 0.
So we're going to look at positions 0 and 1.
And in this particular case, actually 2 is less than 8, so we don't need to swap anything.
So we skip the if statement and just increment J.
So J equals 1.
So we look at 8 and 4.
8 is in fact greater than 4.
So we do swap those 2.
We increment J again.
Right, so another pass through.
Right.
So when J was 0 and then 0 plus 1 was 1, at those two we didn't swap anything.
But when we're comparing 1 and 2, we did swap position 1 and 2.
So when J equals 2, Mariana hit 2 and 3 and 8 is bigger than 2.
So we will swap position 2 and 3.
I have a question.
Yes?
I'm sorry, just when you say after first pass, do you be in the outer for loop?
Yes.
Okay.
Yeah.
Yeah.
Okay.
Thank you.
Yeah, thank you.
So we'll swap 2 and 3.
So when j equals 3, we're looking at 3 and 4 and 8 is bigger than 7.
But then we get to j equals 4 and we stop.
Right.
Because our inner loop is j in range.
I so that'll go from zero to three and it'll stop at four.
So all that this means is that like, yeah, once we've gotten something in the correct position, like it's just settled and we can ignore it.
So now we've gone through another pass and so the next time we go through the third pass, you know, 8 and 10 would correctly placed and we can ignore those two positions also.
It just, it makes it, I don't know, it gives it the appearance of being more efficient like it does in practice.
Cut down on the amount of comparisons that you're doing.
Right.
Because if we didn't have that, then we could get down to a position where only the last two numbers maybe need to be swapped.
But we're still doing all the comparisons all the way up the list, like just for fun, which is, you know, like not the worst thing in the world, but if we can avoid it, you know.
So I'm trying to see if it says it on the board.
What's the big O here?
It's N squared.
I mean this is classic N squared.
And don't be fooled by the fact that, yeah, each time we go through the loop we're looking at one less thing.
But, you know, in the end it's one less thing.
We're still going through enormous amounts of iterations of this loop.
So bubble sort is absolutely.
Which is why Barack Obama is correct and it is not the optimal sort for sorting a million 32 bit integers.
So.
All right, so based on what I have told you about over here, so we talked about the speed of bubble sorts.
Is this sort stable?
Is it adaptable?
Like, is it currently, like, I guess, is it currently adapted and how much memory does it use?
We'll take it and it's a.
About that.
Talk to each other and again, answer the question, is it stable?
Is it adaptable?
How much memory does it use?
It's using four, it's using like four memories.
It's like using, it's stable.
And also like how much is using.
It's like four.
Like how much memory is like using other like a number.
I don't really understand what that means.
Like it's stable but like it's not like using all it's like energy, like memory base for that, like sort.
But it knows if it's sorted because if it's already sorted.
Do you know the room?
Unfortunately, yeah.
Be like, yeah, will be old one or I don't know, you're not talking enough is the thing.
Most teachers don't say, but Here we are.
Okay, so it's all good.
We're good.
So what do we think?
Is this sort stable?
Will it swap the twos?
Sorry, I asked two questions there.
And so is the sort stable?
Okay, yeah, I asked two different questions and they had opposite answers.
And I was like, some people give me a thumbs down.
I'm like, shit, yes, this is stable, right?
Because this is just saying if listed J is greater than.
Right?
So it'll only swap if the two things.
If one is greater than the other, and since these two, you know, twos are two equals two, then, yeah, they will not get swapped.
So global store, at least this implementation is.
How much memory does it take up?
This one's maybe a little tricky because I'm not sure I gave you enough information of a Piper.
Do you want to go for it?
Just going to say it takes up a lot because the O of N is N squared, right?
So.
Oh, I see what you're saying.
Okay, so, yeah, I see where you're going with that.
But keep in mind, when I'm saying, like, how much memory does it take up?
I don't mean.
Yeah, this isn't about, like, how much work it's doing.
It's literally about, like, how much additional, like, space is going to.
I'm assuming it's a lot because I think every time there's a swap, it has to memorize a new list.
Oh, interesting.
Okay, so.
Okay, so I'm glad you said that because that actually then gets into a discussion of, like, wait, how will do Python lists work?
Something we probably have not, in fact discussed in this class.
But I should remember, you know, we discussed this part of how they work.
So, yeah, if we're not making.
If we're not.
If we're not making the list, we're not randomly generating the list or anything.
Right?
Just be O1.
Because you're only ever remembering one guy, right?
And you're forgetting him.
Right, While we're placing him, rather.
Yes.
So, yeah, but this gets into a question that Jodi Piper was referring to, which is like, okay, but is that how lists work?
Right.
The question then is, can we actually change the contents of a list without creating a whole new list?
Because, and this sounds like a simple question, but remember, nothing is simple.
No, so, because here's the thing.
There are data, there are objects and pipes, some of which are mutable and some of which are immutable.
So immutable object can be changed.
Right?
That's in this case, what mutable means.
It doesn't mean it can be silenced.
That's a different type of use language is fun, isn't it?
So can be changed, cannot be changed.
Strings in Python are immutable.
Okay, so in Python, I cannot say W equals word, so I can say, right?
I can access the locations in a string using the same format that I would with a list, right?
So that might give the impression that lists are mutable or the strings are mutable, but they're not.
I can't change the value inside the string.
So if we were trying to sort the letters in a string, we'd be screwed.
Can't do it.
You have to turn into a list first.
Because lists are mutable.
You can change the contents of a list.
We do it all the time.
So, Julie, you're totally right in that if secretly what was happening where every time we wanted to change something in the list, Python was like, oh, crap, and it was making a whole other copy of the list.
Like, that would suck.
But that would mean that we would be using a ton of memory.
But because we can swap around the content inside of a list, it is.
In fact, the memory being used here is just O1 because we're only ever using that little baby temp variable.
And like, I guess I and J, but like.
Okay, yeah, we'll.
We'll swap those.
Yes.
Sorry.
Could you just describe a little bit how you're able to use big O for memory too?
Yeah, it's just.
So the idea here is just like, thinking about how much everyone should say space in memory.
Because I've said that before and that was obviously not helpful.
But imagine like, if you're storing a list, right?
You create a list in your computer and then you're saying, like, okay, we need to sort it, or like, we need to do something with it.
If we make a whole other copy of the list that's the same size, then we'd use O of N memory.
We'd use N memory, right?
Because, like, there's N things in the list.
We made a copy, now it's again N.
So we kind of just think about it in terms of, like, how much additional room do we need to make this sort work?
And in the case of vocal sort, we just need, like, okay, we need three, we need IJ and 10, but that's it.
So we're good.
We don't need to, like, have a whole lot of extra stuff going on.
So we can just call that O of one.
Is it?
Okay, so bubble sort, stable, nice memory.
O of one.
Is it adaptable?
So it is not currently adapted, right.
Like, it is not currently capable of checking to see if the list is already sorted.
All of this will always go through.
Not the entire list, but it'll check, you know, 0 and 1, 1 and 2, 2 and 3, 3 and 4, 4 and 5, and then 0 and 1, 1 and 2S, 2 and 3, 3 and four, and then 0 and 1, one and two, two and three, and then 0, 1, 1 and 2.
I'm so glad I only put five things in this list.
Six things I can't count.
But we can make bubble sort of.
Like, we can adapt it.
Because the neat thing about bubble sort is we can check to see.
Like, if we go through an entire iteration of this inner loop and don't make any swaps, then we can say, I think we're done.
Like, there's nothing out of place, so we can stop.
Let me prove it with the shorter list this time.
So if I have the list 2, 4, 6 and 3, like, we're so close to being sorted.
This is agonizing, but we're almost there.
So we can go through and we can compare two and four and say those are good.
No swaps.
We can go four and six.
Those are good.
No swaps.
Six and three.
We want to do swaps.
So maybe we add a little something to this code, like a Boolean variable that says, like swaps equals false, just as an example.
And then if we get into that if statement, we can say, oh, damn, swaps equals true.
So if we get to the end of the inner loop and we found that swap is in fact true, then we know, all right, we had to move something, but maybe.
So we'll need to check one more time, because if we had to swap one thing, maybe the list is sorted, maybe it's not.
We can't tell.
But if we go through the list one more time and say, okay, two and four are three and three.
Oh, yeah, three is there three.
Two and four.
Good.
Four and three.
This is a bad example.
I should have put three first.
Oh, well, need to swap.
Okay, so we're not done yet, but we can swap those two and we could do 2, 3, 3, 4.
We're good.
If nothing is swapped, we know that the list is sorted.
There's no way for bubbles to.
To work where you go through and do zero swaps and still have the list be unsorted at the end.
It's just.
It's not possible.
And the book, in fact, has an example of that.
So they have.
They call it exchanges, not false.
Whatever.
Exchanges Equals false.
And then, yeah, if there is in fact a swap, a exchanges equals true, if not exchanges.
So at the end of that inner loop, if exchanges is still false.
Yeah, if exchanges is still false, they use break.
I hate that.
But since they're using a for loop, I'm designed using wild true.
So yeah, so now this version of bubble sort is adapted.
Like it can check to see if it sorted and it will stop if it's going through.
And it says like, yeah, we didn't have to swap anything, so we're good.
I also want to point out that it is using this very special python ability to swap to variables without two locations in the list without using a temp variable.
Python can do this, right?
So all this is saying is like, hey, take these two values J and J1 and then put J in J1 and J1 in J.
This is very cool.
This is a nice thing that python does.
Don't get used to it.
Most other languages will.
Will not do this.
Java.
Absolutely not.
See, you wish.
I don't know about JavaScript, obviously, just because it'll look kind of crazy shit.
So who knows?
That's my zone.
She can tell you.
But like, it's nice to have this.
But don't assume that that will work in every programming language.
Most of them will not support that kind of syntax.
Just the friendly warning.
But yeah, this is a neat.
So that's a neat trick.
And this is adaptive global source.
So adaptability can be.
Yeah, we can have a version that checks and you can see we didn't have to add a whole lot of extra code in to make that work, right?
Yes, so is.
So if the next placement is not greater.
Wait, I'm trying to understand what the exchanges does.
Okay, so exchanges is just a extra marker that's checking to see, like, have we made any swaps?
So before the inner for loop, we set it to false to say we haven't made any changes.
But if we go through.
So if we were to go through a sorted list, right?
So 4J and range.
So we'll start at zero.
This is our first time through the list.
Exchanges equals fossil.
If we're going through the list, then we compare 2 and 4, those are good.
4 and 6, those are good.
6 and 8, those are good.
8 and 10, those are good, Right?
So we get through the whole list, we make zero swaps.
So at the end of it, exchanges is still false.
So this says if not exchanges, if not false, not false is true.
That's a weird one.
How many of you have taken a logic class or like done discrete places.
Okay, yeah, there is some logic in discrete.
That's right.
Okay, so just a real quick refresher in case you don't know this.
So if we say right, so true is true, but if we say not false.
Right, not false.
So we're negating false.
Not false is true.
So if not false turns into if true.
If true is true.
Like true is true.
I don't have a better way to say that.
So then we break out into.
And we just say, yeah, we're done.
We don't need to check anymore because there were no swaps.
So if there are no swaps, then exchange is true.
Yes.
No, then exchange is false.
Exchange becomes true.
If we do a swap.
Right, That's.
It's inside the if statement.
So if we do a swap, then we say, then exchanges becomes true and then if not true, not true is false.
Okay, cool.
Yeah.
The people in this book who wrote this book really, really love to just have these if statements that just evaluate, like straight to true or false.
If you're more comfortable saying, like, if exchanges equal, equal false, or something like that, that is totally fine because they just love to throw in a knot and be like, our job here is done.
And it's like, yes, technically.
But is this readable?
Yeah, you're taking a logic class, but, you know, never have.
Scarlett, how would you write this without break?
You would have to, I think, turn the outer for loop into a while loop and just have a count down.
So just because I don't think in Python you can force I to change.
There's some languages where you can, like override I, but I don't think you can do that in Python.
I feel like you can do it in Java, though.
It's been a while, Professor.
Yeah.
So the goals that you showed are if swap have equals equals true, then exchanges equals equals false.
So this is.
So this is just another way of saying if exchanges equal to false.
Yeah.
And the part that affects.
It's just that.
So we're starting off by assuming that we're not going to do any swaps.
So we set exchanges equal to false and then if we do have to do a swap, we change it to true.
So that means like, hey, we swapped something.
The list was not sorted.
Let's go back and check one more time and see if it's sorted now.
Yeah.
Okay.
So we.
So for those of you who like visualizations, which, I don't know, some people do, people don't.
We have the book includes this very nice little like.
So it's just going through and it's showing that each pass through the loop we're taking, that we're finding the next biggest thing and moving that up.
So each time this is for going to be a lot clearer on your own laptop than it is up here because the projector is not doing a great job with the red.
It kind of looks like it's highlighting multiple things at a time.
But that's okay.
We'll do the best we can with what we have.
So for those of you who like visualization, the book does include them for all of these.
For those who like slightly more abstract visualization organizations, today is your lucky day because there is a group from Eastern Europe and they have done dances IBU can't help people customize and save to traditional Eastern European music.
This one's Hungarian.
To represent different sort of algorithms.
I asked what you doing here?
I don't know.
Right.
So we have an UNSC list and yes, I'm going to narratives for you.
Unfortunately, I do not know enough about.
So 3 started at position 0, right.
And swapped with 01.
3 and 8 are now comparing and they go, no, we're good.
We're not going to swap.
So but we keep moving the marker that keeps track of where we are.
So eight is now the biggest value that we found so far.
So 8's going to keep comparing itself to the other numbers.
So we're always moving down two positions next to each other.
So 8 and 9.
9 is in fact already prepped in place.
So 8, 9 is going to prepare and then we go.
We're good.
And we go back to the beginning.
So ye.
But we're just gonna keep swapping like that.
Ever so wonderful.
I agree.
Okay, so this is actually a brand.
Believe it or not.
An important thing just happened in this Hungarian.
Some.
I don't know how to pronounce that and I don't want to mess it up.
So what just happened was we compared all the way up.
So six moved up, seven turned around, six didn't.
Right.
Even though we know intellectually that six is correctly placed now, the algorithm doesn't.
Right.
The algorithm's like.
All I know is I've done this enough times.
7 is in the right place.
That's all I can say for sure.
So six, even though we can see that six is fractured, place is not turned around yet because the algorithm is not smart.
So it's just going to keep checking.
Right.
And we can glue down here too.
Everyone's like getting Correctly placed, but bubble sort doesn't know that.
So five and six slots compare, even though, like, we know that they're correct.
Equates.
And now we're about to find out, is this an adaptable sort?
Have they.
Have they implemented the correct invitation on their own, or will we have to keep going?
They sometimes I have guessed, but.
Okay, so they.
They have an adaptation.
They said, like, we can tell that we're done.
Are there, like, more of these throughout the semester?
They have one for every single sort, and they have at one point since practice.
So, like, is this not the best thing?
That was actually really helpful.
I do wish it was better than, like, a bunch of X's all on top of each other.
I mean, that's fair, but, you know, I.
I am but one person, and I don't have a dance.
You need to clone yourself and do dances.
Believe me, you don't want to say that.
My only complaint here is I do wish that they actually, like, included at least the pseudocode of the representation because I think it would be helpful to show, like, what version of this that they're doing.
But they don't.
So we kind of have to, like, I knew I underwater.
Okay.
Sounded like she was underwater.
So.
But yeah, they do have different versions for all of the different sorts.
So what?
Let's try which one?
Quicksort Sounds very promising.
It does, it does.
It's also a little bit of a lie, but we'll get to that next week.
So in the first week, what I usually like to do are some of the, like, the simpler sorts.
Because just wrapping your head around, like, how all these variations work can get a little bit tricky.
So let's just check and see what does the book actually do next.
Okay, so I'm trying to think if it would be absolutely weird if I just showed you the video and had you guessed how it works.
That would sound great.
That sounds great.
I mean, we only have, like, 15 minutes left, so I guess, like, let's see how it goes.
All right, so pay attention and try and figure out.
How does collection short work?
Okay, so I will tell you that we just finished one iteration of the inner loop of the selection sort.
I know, right?
What happened?
Basically, just, like, validated his spot in the lit list.
Like, it looked like he just compared himself to every other number or every other spot.
And then when this is how we started.
Oh, wait, yeah.
Okay, so.
But you're right.
Like, at the end of the first loop, did we start with the first number and then basically find the lowest Number by comparing everyone.
Yes.
Okay.
Yep.
So the very first few steps here, three comes out, right?
And it's like, okay, I'm a small number so far.
Let's see who we've got.
And then zero comes out and is like a brawl.
Guess what?
So we do a fancy little spin spot and now you're right.
Zero compares yourself to everything else.
So.
Yeah, but that's hard to spot, right.
Because of the tiny little switch that happens.
So then zero would go back to zero and then who comes out?
Perfect question.
Okay, so we are.
See if I get to the right spot here.
No spoilers.
And you're actually.
Actually, I should have paid more attention to the time stamp.
Sorry about that.
Zero.
Come on.
There we go.
What do you think?
The big oh of selection.
Sort of.
So this isn't me doing it, but yeah.
So one came out, one compares herself to three.
Is this worse than bu.
They're both N squared it.
There's another thing.
There's a few other ways we can look at certain sadness and we'll get to that.
Check them all, though.
So, yeah, so one is comparing to every other location in the list.
We find that one is in fact the next smallest number.
So one will go back to where she was before.
Three's out again.
Looks boy.
So three of them compared to two, and now they're going to swap.
Right, so three takes two's place and two continues.
Yeah.
This is so bad.
So two goes on to compare myself to the rest in the last two.
Spoiler is going to be less than both nine and six.
So.
So two goes into place, eight comes out and we know.
So, like, this isn't going to work.
Right?
There's going to be a lot of swaps or, like, a lot of switches going on because eight is bigger than seven.
So right now, seven is the smallest number that we found, but seven is greater than three.
So they're going to swap three.
Oh, yes, three.
Yeah.
Also, like, so much respect for the ones who are already sorted and they're just like, over here.
Just like.
Yep.
If we are still doing it, if this video is 7 minutes long stuff, I can't end how long in, like, real life, it takes at least 20 minutes.
Yeah.
So, yeah, so Facebook.
I think that's part of it.
Yeah.
I mean, you know, but honestly, again, I'm not an expert in Eastern European folk dances, so, like, don't.
They're going faster.
They're definitely going faster.
Yeah.
This is just such a.
An interesting way to teach.
Did people just, like, decide That I don't know.
Or does it, like, actually get thrown out?
Oh, we put the end speed increase every time.
It's a.
Yeah.
Whistle.
Yes.
No one.
There's no.
She just gets to do a little.
Jim.
I will also know that this video was made 13 years ago.
So it's been around for.
They've been around for a while.
But some of the videos are like.
I have no idea why they're.
I will not click on that right now.
We don't have time.
Okay, so a selection sort.
So as you figured out, hopefully from watching that dance, what happens each outer, like each old video chip out, like each iteration of the outer loop.
So as we go through the entire thing, so the inner loop is going to go through and find the smallest unsorted Anything like that, definitely make sure you fill it form whatever.
We have to do it a couple days before.
I don't remember the exact.
But yeah, make sure you do that.
Okay.
So talking about finding and implementing them, and I already kind of told you that when we do the implementation for a binary search tree, we are actually going to go back to using nodes rather than trying to do it as an array.
And there's a couple reasons for that, right?
So in a binary search tree it is, as we noted last time, first of all, totally possible to have a tree that effectively is just a fancy line.
And to display this in an array is going to be really gross and ugly and take up lots of memories.
So we don't love that.
Now next week when we get to balance binary trees, we won't have that option, so we'll generally be a little bit better.
But the other part of this is if you have a binary tree that is, you know, maybe not quite so unbalanced, but has a little bit of oddness to it.
If we were to put this in another.
So let's say actually put values 30, 80, 75.
If we were to put this into an array, none, 70, none, and then two more nums, 60, 75, gross.
Not a great use of memory really when you think Anything like that, definitely make sure you fill it form whatever.
We have to do it a couple days before.
I don't remember the exact.
But yeah, make sure you do that.
Okay.
So talking about finding and implementing them, and I already kind of told you that when we do the implementation for a binary search tree, we are actually going to go back to using nodes rather than trying to do it as an array.
And there's a couple reasons for that, right?
So in a binary search tree it is, as we noted last time, first of all, totally possible to have a tree that effectively is just a fancy line.
And to display this in an array is going to be really gross and ugly and take up lots of memories.
So we don't love that.
Now next week when we get to balance binary trees, we won't have that option, so we'll generally be a little bit better.
But the other part of this is if you have a binary tree that is, you know, maybe not quite so unbalanced, but has a little bit of oddness to it.
If we were to put this in another.
So let's say actually put values 30, 80, 75.
If we were to put this into an array, none, 70, none, and then two more nums, 60, 75, gross.
Not a great use of memory really when you think Anything like that, definitely make sure you fill it form whatever.
We have to do it a couple days before.
I don't remember the exact.
But yeah, make sure you do that.
Okay.
So talking about finding and implementing them, and I already kind of told you that when we do the implementation for a binary search tree, we are actually going to go back to using nodes rather than trying to do it as an array.
And there's a couple reasons for that, right?
So in a binary search tree it is, as we noted last time, first of all, totally possible to have a tree that effectively is just a fancy line.
And to display this in an array is going to be really gross and ugly and take up lots of memories.
So we don't love that.
Now next week when we get to balance binary trees, we won't have that option, so we'll generally be a little bit better.
But the other part of this is if you have a binary tree that is, you know, maybe not quite so unbalanced, but has a little bit of oddness to it.
If we were to put this in another.
So let's say actually put values 30, 80, 75.
If we were to put this into an array, none, 70, none, and then two more nums, 60, 75, gross.
Not a great use of memory really when you think Anything like that, definitely make sure you fill it form whatever.
We have to do it a couple days before.
I don't remember the exact.
But yeah, make sure you do that.
Okay.
So talking about finding and implementing them, and I already kind of told you that when we do the implementation for a binary search tree, we are actually going to go back to using nodes rather than trying to do it as an array.
And there's a couple reasons for that, right?
So in a binary search tree it is, as we noted last time, first of all, totally possible to have a tree that effectively is just a fancy line.
And to display this in an array is going to be really gross and ugly and take up lots of memories.
So we don't love that.
Now next week when we get to balance binary trees, we won't have that option, so we'll generally be a little bit better.
But the other part of this is if you have a binary tree that is, you know, maybe not quite so unbalanced, but has a little bit of oddness to it.
If we were to put this in another.
So let's say actually put values 30, 80, 75.
If we were to put this into an array, none, 70, none, and then two more nums, 60, 75, gross.
Not a great use of memory really when you thinki number and then it will place it.
So after each iteration of the outer loop, we have one more number correctly placed.
In this case, we're doing smallest.
I believe you can.
You could do it with the largest.
Traditionally, though, you kind of go through and find the small, the next smallest unsorted number.
So just like in the dance, you know, we're gonna.
Oh, so actually this version does do the largest.
I apologize, I forgot.
This particular book selects for the largest.
You can do it either way.
Right.
You just have to pick one and go with it.
So the dance did smallest, the book does largest.
It doesn't matter.
Just be consistent.
So this goes through it finds the small, the largest number, this version, and then places it.
And then.
So 93 will be the corrected place and we have 77 and swap that.
So wherever the largest number that we find is, it gets swapped with the.
In the place where it needs to be, which I believe is actually not what the selection.
I said is a great question that I'm not going to answer right now because that is the right question.
So.
Yeah.
So Bella earlier asked a question about, like, well, is this better or worse than Flexion?
So technically.
Technically.
Or bubble sort, Technically, they are both O of N squared.
They both have nested for loops.
They're both doing a whole lot of work.
But the things that we look at, clearly, selection sort was slower than bubble sort.
Somehow they're both N squared.
But, like, they did not have to speed up bubble sort the way they did selection sort.
Right.
I think it's worth noted that in selection sort, they'd also do a lot of, like, extra load jigs.
That is true.
Yeah.
But I mean, they just saw a learning bubble sort too.
So the things that we look at.
So just as a quick like thing something to pay attention to the things the other the things that we can look at for sorting algorithms to compare them is number of comparisons and number of swaps.
And we will find that different sorting algorithms, even if they both run in N squared time will have different numbers of comparisons and different numbers of swaps and that those can still you know, in terms of like actual run like how long does it take to run this in the real world can have a huge impact.
So yes this is a note.
Big O does give us an overall sense of how the algorithms work but you can still find that like if you actually run a different algorithm on an actual list like bubble sort might take significantly less time to selection sort even though nominally they're the same.
Yeah.
Okay, that brings us to the end of class