So I want to go back and I want to do another implementation where our input is truly something that we would consider to be a list.

There are a couple of reasons we're doing this, partly it's because of the next thing we're going to look at, which is trying to prove that it's actually correct.

Okay, so let's go back, we'll go through sorting the exact same data we had before.

Whoops, my debugging duck is in the way.

So currently we don't have any data, I guess we could consider that to be completely sorted already.

So let's go back and look at the same sort of data set that we had before.

Okay, this time I'm going to assume that this is a list.

I'm going to separate my numbers just to indicate that I don't really mean for this to be an Just like before, we're going to work through from left to right to find our candidate for the lowest value, the minimum.

Two looks pretty good, I get to 34, I get to 1, that's a better candidate than 2. 34, 3, 89, 13, 55.

Now here's where we're going to depart from our previous approach.

Instead of swapping elements around, I'm going to literally remove an element from our list, and our list shrinks down to a smaller size.

And we append the element to a new list.

So I'm going to go through the process again, 2 is a pretty good candidate, 34, 3, 89, 13, 55, none of those are better than 2, so I remove 2 from my list.

The list gets a little bit smaller, 2 gets appended to my solution list.

Repeat the process again, 34 is pretty good until I see 3, and then 89, 13, and 55, 3 gets removed from my list and appended to my solution list.

Repeat the process again, 34 seems pretty good, it's definitely better than 89, but 13 is better than 34, 55 isn't any better than 13, so we remove the 13, shrink our list down, and append our 13 to our solution.

And we continue this process again, and again, until the last item is removed.

And just like before, we've added all of our data to our list in order from smallest to largest, the data is completely sorted.

One of the real big distinctions here, however, is that we destroyed our initial list and created a new list instead of swapping things around in place.

Okay, so as a programming review, let's look at some code that's going to implement this.

So just like before, I've got an array of values that represents my data, and this time I'm going to put it in an array list.

So it's technically a list, but it does have an array to kind of support or hold the data.

So we'll look at this more in depth this week.

So our overall goal is to have two different lists, one that represents our input values that's already been constructed, and another one that will be our sorted data.

So I'm going to create an array that represents the sorted data, and it'll be initially an empty array list, a brand new array list.

Then I'm going to prototype how I'm going to use this new method.

Okay, so I'm going to call my selection sort, and I'm going to provide it with these two lists, the input list and the sorted list.

Okay, then when I'm done, I'd like to print out my list to make sure that it is in fact sorted.

Okay, so I've kind of set up my problem.

It's time to go and create a method.

So it's going to be a public static method with a void return value, and it's going to have those two parameters, the two lists, the list of input and the list that will represent the sorted data.

Okay, so now we have to figure out how to solve our problem.

So just like when I was working with this on the table, I'm going to process data while there's still data in the input.

And basically what I have to do is find the minimum value in that input.

So I'm using a counting for loop here.

By the way, this has some subtle side effects that we'll look at in a little bit.

But just like before, I'm creating a variable to keep track of where I found my best value, and I'm going to go through and compare each value to the best one I found so far.

And if it happens to be a smaller value, I will update where I think the location of my best value overall is.

Okay, so when I'm all done with the loop, I've found the minimum values location.

So now I can get the minimum value, and I need to add it on to my sorted list.

Okay, now that I've added on to the sorted list, I might as well remove it from the input list.

Okay, and that's it.

Let's run it and test it and see if it sorts our little sample list.

And in fact, it did.

Okay, now I'm going to do something additional here.

I'm going to go through a process called instrumentation.

So the idea of instrumentation is augmenting code in various ways to track performance and gather data about it.

In this case, it's going to be a really, really, really crude form of instrumentation.

I'm just going to add in some additional print messages, and we'll try and use those to get a sense of how long it takes this code to run.

So I'm going to put a print message before I do my sorting that says I'm starting.

I'm going to put another print message after I do my sort that says we're done.

Okay, then I'm going to run my program, and it printed everything almost instantaneously.

There seemed to be no significant difference in time between when it started and when it finished.

So I'm going to go up, and I'm going to change the data that I'm supplying.

And so instead of supplying it just a little bit of data, I'm going to change this for loop.

And I'm just going to append a whole bunch of data.

So instead of using my previous values, I'm just going to generate random integers.

So I'm going to be using math.random here.

I know that math.random gives me a double number, and I want to end up with an int at the end.

So I'm going to do some typecasting.

Basically, what this is doing is it will give me a random integer between zero and the maximum possible integer value.

Then I'm going to change my loop.

I'm just going to try and have it count up to 10,000.

I'm using a notation you can use in newer versions of Java.

Oh, wow, that was quick.

So it sorted 10,000 items really, really quick.

Let's try 20,000.

That was pretty quick, too.

Let's try 30,000, maybe.

One, two.

Okay, so that was maybe a second.

That was at least noticeable, right?

40,000.

One, two.

Pretty quick, too.

But about two seconds, maybe.

Two to three seconds for 40,000 items.

Now, that was on my computer.

My computer is several years old.

Your computer might be faster, so maybe they'll run quicker for you.

Or maybe your computer is a different model with a different processor, and it'll run slower.

So this is an empirical test.

It's an experiment.

I was measuring how long it would take.

Now, let's look at something interesting.

So I used an ArrayList.

But an ArrayList and a LinkedList are somewhat interchangeable.

I mean, they've got the same operations.

So let's see what happens if we do a search and replace, and replace the ArrayList with a LinkedList.

So I'm going to search for all of the places where ArrayList is used.

And we'll replace it with LinkedList.

OK.

Now, before I get carried away, I think I'm going to back down.

I'm going to test out my simple original sample problem.

So I'm going to put in the loop that uses my original test values there.

I'll run it with those values.

Oh, yeah.

OK, that's cool.

So it ran, sorted my six or so values there.

It looks good.

OK, seven values.

Let's go back and try it again with more data.

So I'm going to put my loop back in.

I'm going to set it at 10,000.

One, two, three.

Wow, if you remember, the ArrayList version took about two seconds.

But this is taking forever.

OK, so a very subtle change there had a huge impact on performance.

Huge.

I mean, we're still waiting for it to finish.

Now, this does not mean LinkedLists are bad.

LinkedLists have some really great strengths.

But they've got some weaknesses, too.

And I have used a LinkedList in a poor way.

I could restructure this in ways where a LinkedList would perform just as well as the ArrayList did.

So this is one of the big takeaways from this class, understanding all of these subtle distinctions and how just a subtle change can have a huge impact on overall program performance.

Thank you.