ZAMYLA CHAN: Let's implement sort.
For this problem, we're going to take an integer array
and then write maybe a selection sort or a bubble sort
in order to sort the array in order from smallest to largest integer.
Let's look at selection sort first.
Selection sort is an algorithm that finds the minimum value in an array
and then moves it to the beginning and then selects the next minimum value,
moves it to the beginning, so on and so forth.
So let's walk through an example with just this simple array
of five integers.
I'm going to start by creating a variable, i, that looks
at the very first index of my array.
Now, because I've only looked at one value so far,
I'm going to set my minimum to that index, 0,
because I haven't looked at the rest of the array yet.
In order to look at the rest of the array,
I'm going to create a new variable to iterate.
Let's call that j.
So I'm going to use j to iterate over the remainder of the list
and try to find the minimum value in my array.
The value at j, in this case, is 5.
And 5 is greater than 3.
And so the minimum index doesn't change.
Moving on, iterating over the rest of the array,
j is now at 2, which contains in this case the value 2.
2 is less than 3, and so my minimum index changes to the index 2.
I increment j once more.
Now, the value stored at index 3 is the value 1.
1 is less than 2, and so yet again my minimum value changes to the index 3.
Finally, I have one more element to compare.
At index 4, the value 4 is greater than 1.
And so my minimum index doesn't change and remains at 3.
So what I do next is I take that value and I swap it with the value at i.
And there, I've locked in the first minimum value of my array.
Moving on I can then safely keep that value locked in
and look at the next value in my array.
i is going to start at 1 then, where the value 5 is located.
I haven't looked at the rest of my array yet.
So I'm going to set my minimum index to 1.
I'm going to use my iterator variable j.
And I look at then the index 2, where the value 2 is less than 5.
And so the minimum index is now 2.
Iterating j again and again, I find that the minimum value is still
located at index 2.
And so I take the value at my minimum index,
and I swap it with the value at i.
And there I have another integer locked in.
I increase i now.
I do the same thing where I set the minimum value to the first value
that I look at.
I iterate over.
And in this case, we find that the minimum value is located at index 3.
Swapping those, then I look at the last two values, iterate over again.
And then finally, after I've completed that last swap
and I only have one value left, I can lock that in as well.
And there I have a sorted array, 1, 2, 3, 4, 5.
Take some time to create some examples for yourself
and walk through the selection sort.
Then, we can talk about this pseudocode.
I'm going to propose that from i equals 0 to n minus 2,
that is the second to last element in our array,
we're going to set the minimum index to i.
And then, we're going to iterate over the rest of the list finding
the smallest element from i to n minus 1, the very end of the array.
And if at the end of comparing them all the minimum index isn't at i,
then we're going to switch those elements, the one at minimum index
with the element at the i index.
Once we've completed that and iterated over the whole list,
we have a sorted array, where we have the minimum values being
selected to go to the beginning.
That was selection sort, where we take the minimum values
and we move them to the beginning.
Now, bubble sort will actually take the largest elements
and bubble them to the end.
Bubble sort will iterate over our array, comparing adjacent elements.
Every time a comparison is made, we're going
to swap any elements that are in the wrong order.
And once we don't make any swaps, then that means the list is sorted.
Let's look at the very same array, but now apply a bubble sort.
I'm going to start by looking at the first two elements
at index 0 and index 1.
3 is less than 5, so as of now, the array is in order.
I increment both my left and right indices,
and I find that 5 is greater than 2, and so I swap those two values.
Incrementing my indices again, 5 is greater than 1, so that gets swapped.
Incrementing again, 5 is greater than 4, so that gets swapped.
So you'll see here how 5 bubbled all the way to the end.
I can lock that in now.
I go back to the beginning.
Compare the values at 0 and at 1.
3 is larger than 2.
So that gets swapped.
3 is larger than 1.
So that gets swapped.
Now, 3 is not larger than 4.
And so I don't make any swaps.
So I can then lock in the value 4.
I go back to the beginning.
2 is greater than 1.
I swap those.
2 is not greater than 3.
I don't swap, and I lock that in.
Comparing once more, 1 is less than 2.
So no swaps are made.
And thus, I have sorted my list.
And there we have a sorted array.
My name is Zamyla.
And this was sort.