0:00

[MUSIC]

In the previous video, we implemented selection sorting Java, and

then we stopped and thought about some questions to do with this algorithm and

how well it performs.

So, so far in this course we haven't really asked ourselves whether algorithms

are correct and how well they run, and so let's take a few minutes now to

think about how we might even formulate answers to these questions.

So let's think about correctness first.

We had a problem that of sorting an array,

meaning organizing the information in the array.

And then we had a candidate strategy, selection sort, that we think did

pretty well, and we think that it really does organize the elements in the array.

But if this was a really mission-critical problem that we are trying to solve here,

it's not enough for us to just sort of say hm, yeah, I guess it's gonna work.

Hopefully there won't be any bugs.

All right, we want to be certain and

convinced that our algorithm is really going to do what it's supposed to do,

no matter what edge case we throw at it or how big an array we give it.

And so let's think back to the high-level picture we have of selection sort, and

think about how that high-level picture can give us

confidence that the algorithm works.

So remember what we're doing in selection sort is, at each step through the for

loop, we're looking at a new position in the array and

we're swapping into that position in the array the element that's going to be there

when the array is really truly sorted.

And so what we have is some initial piece of the array that is sorted,

and it keeps growing each time.

And so as this sorted part of the array, the dark gray part of the array, grows

with each iteration of the foreloop, more and more of our array is in good shape.

It's organized and it's sorted.

And so, by the time we finish the foreloop and

have gone thought the entire length of the array, then our entire array is sorted.

And so, this argument that we just went through can be completely formalized and

can be used to prove the correctness of selection sort.

Okay, so we're convinced that it works, but how well does it work?

And what does that even mean?

And so the question of performance is a really tricky one but

a super critical one.

And it makes the difference between a very sluggish

computer that no one really ever wants to use because it takes seconds between when

you click a mouse and when it actually responds, to a super snappy computer that

everyone is really happy running apps on and maybe even multitasking.

Because performance we can measure with time, we can measure with resource use,

and the experience of how an algorithm runs makes a big difference to

how far we can push that algorithm and how big a dataset we can expect it to work on.

So it turns out that selection sort, even though it's correct, doesn't do so

well when we think about its performance.

It turns out to be a very slow sorting algorithm.

Now we won't talk about the details of what it means for

one algorithm to be slower than another, and how we can compare algorithms,

when their performance might depend on their input in this course.

But we will talk a lot more about it in the next course.

And so, stay tuned, it's a beautiful theory of computation and

complexity that we'll get to in a little while.

Now, what I wanted to mention though, is that aside from performance issues and

somewhat motivated by performance issues, we're always on the hunt for

other algorithms for solving even the same problem.

So we had this sorting problem, and we had one solution for

it, namely selection sort.

But, even if we did not know that it was kind of a slow one and maybe not so

great, we'd still be interested in finding other algorithms that solves sorting.

And that motivation for

finding other algorithms comes from recognizing that in the real world

different contexts might require different properties from our algorithms.

Sometimes, we might have a nearly sorted list,

a list that is usually pretty organized but occasionally we add on to it.

Maybe as new computers join a network or as new people join a team.

And so, we might want an algorithm that responds really well to almost sorted data

and is really fast in that situation.

On the other hand, we might have a context where our data is going

to be coming from all over the place and is not organized at all,

but maybe is not going to change too often.

And so maybe we have a different algorithm that doesn't respond so

well to dynamically changing data, but

does really well even if the incoming information is completely unorganized.

So, even if one algorithm is often slower than the other,

it might still be useful for other reasons if we know something

about the problem that we're solving and the real world contact that we live in.