1
00:00:00,000 --> 00:00:00,570


2
00:00:00,570 --> 00:00:02,780
ZAMYLA CHAN: Let's implement sort.

3
00:00:02,780 --> 00:00:06,350
For this problem, we're going
to take an integer array

4
00:00:06,350 --> 00:00:10,550
and then write maybe a
selection sort or a bubble sort

5
00:00:10,550 --> 00:00:16,100
in order to sort the array in order
from smallest to largest integer.

6
00:00:16,100 --> 00:00:18,290
Let's look at selection sort first.

7
00:00:18,290 --> 00:00:22,370
Selection sort is an algorithm that
finds the minimum value in an array

8
00:00:22,370 --> 00:00:26,930
and then moves it to the beginning and
then selects the next minimum value,

9
00:00:26,930 --> 00:00:30,330
moves it to the beginning,
so on and so forth.

10
00:00:30,330 --> 00:00:33,650
So let's walk through an example
with just this simple array

11
00:00:33,650 --> 00:00:35,420
of five integers.

12
00:00:35,420 --> 00:00:39,020
I'm going to start by creating
a variable, i, that looks

13
00:00:39,020 --> 00:00:41,760
at the very first index of my array.

14
00:00:41,760 --> 00:00:45,350
Now, because I've only
looked at one value so far,

15
00:00:45,350 --> 00:00:48,110
I'm going to set my
minimum to that index, 0,

16
00:00:48,110 --> 00:00:51,410
because I haven't looked at
the rest of the array yet.

17
00:00:51,410 --> 00:00:53,580
In order to look at
the rest of the array,

18
00:00:53,580 --> 00:00:56,030
I'm going to create a
new variable to iterate.

19
00:00:56,030 --> 00:00:57,770
Let's call that j.

20
00:00:57,770 --> 00:01:00,860
So I'm going to use j to iterate
over the remainder of the list

21
00:01:00,860 --> 00:01:06,260
and try to find the
minimum value in my array.

22
00:01:06,260 --> 00:01:09,210
The value at j, in this case, is 5.

23
00:01:09,210 --> 00:01:11,390
And 5 is greater than 3.

24
00:01:11,390 --> 00:01:15,110
And so the minimum index doesn't change.

25
00:01:15,110 --> 00:01:17,600
Moving on, iterating over
the rest of the array,

26
00:01:17,600 --> 00:01:22,890
j is now at 2, which contains
in this case the value 2.

27
00:01:22,890 --> 00:01:29,200
2 is less than 3, and so my minimum
index changes to the index 2.

28
00:01:29,200 --> 00:01:32,100
I increment j once more.

29
00:01:32,100 --> 00:01:37,010
Now, the value stored at
index 3 is the value 1.

30
00:01:37,010 --> 00:01:44,220
1 is less than 2, and so yet again my
minimum value changes to the index 3.

31
00:01:44,220 --> 00:01:47,060
Finally, I have one
more element to compare.

32
00:01:47,060 --> 00:01:50,490
At index 4, the value
4 is greater than 1.

33
00:01:50,490 --> 00:01:54,950
And so my minimum index doesn't
change and remains at 3.

34
00:01:54,950 --> 00:02:02,180
So what I do next is I take that value
and I swap it with the value at i.

35
00:02:02,180 --> 00:02:08,169
And there, I've locked in the
first minimum value of my array.

36
00:02:08,169 --> 00:02:12,730
Moving on I can then safely
keep that value locked in

37
00:02:12,730 --> 00:02:16,400
and look at the next value in my array.

38
00:02:16,400 --> 00:02:21,610
i is going to start at 1 then,
where the value 5 is located.

39
00:02:21,610 --> 00:02:23,500
I haven't looked at the
rest of my array yet.

40
00:02:23,500 --> 00:02:27,460
So I'm going to set
my minimum index to 1.

41
00:02:27,460 --> 00:02:30,370
I'm going to use my iterator variable j.

42
00:02:30,370 --> 00:02:35,180
And I look at then the index 2,
where the value 2 is less than 5.

43
00:02:35,180 --> 00:02:38,830
And so the minimum index is now 2.

44
00:02:38,830 --> 00:02:44,860
Iterating j again and again, I find
that the minimum value is still

45
00:02:44,860 --> 00:02:47,620
located at index 2.

46
00:02:47,620 --> 00:02:51,040
And so I take the value
at my minimum index,

47
00:02:51,040 --> 00:02:53,650
and I swap it with the value at i.

48
00:02:53,650 --> 00:02:58,030
And there I have another
integer locked in.

49
00:02:58,030 --> 00:02:59,860
I increase i now.

50
00:02:59,860 --> 00:03:02,980
I do the same thing where I set the
minimum value to the first value

51
00:03:02,980 --> 00:03:04,030
that I look at.

52
00:03:04,030 --> 00:03:05,360
I iterate over.

53
00:03:05,360 --> 00:03:11,170
And in this case, we find that the
minimum value is located at index 3.

54
00:03:11,170 --> 00:03:16,280
Swapping those, then I look at the
last two values, iterate over again.

55
00:03:16,280 --> 00:03:19,390
And then finally, after I've
completed that last swap

56
00:03:19,390 --> 00:03:23,990
and I only have one value left,
I can lock that in as well.

57
00:03:23,990 --> 00:03:29,200
And there I have a sorted
array, 1, 2, 3, 4, 5.

58
00:03:29,200 --> 00:03:31,660
Take some time to create
some examples for yourself

59
00:03:31,660 --> 00:03:33,670
and walk through the selection sort.

60
00:03:33,670 --> 00:03:36,890
Then, we can talk about this pseudocode.

61
00:03:36,890 --> 00:03:41,530
I'm going to propose that
from i equals 0 to n minus 2,

62
00:03:41,530 --> 00:03:44,500
that is the second to
last element in our array,

63
00:03:44,500 --> 00:03:48,010
we're going to set the
minimum index to i.

64
00:03:48,010 --> 00:03:51,040
And then, we're going to iterate
over the rest of the list finding

65
00:03:51,040 --> 00:03:56,690
the smallest element from i to n
minus 1, the very end of the array.

66
00:03:56,690 --> 00:04:01,240
And if at the end of comparing them
all the minimum index isn't at i,

67
00:04:01,240 --> 00:04:05,320
then we're going to switch those
elements, the one at minimum index

68
00:04:05,320 --> 00:04:08,320
with the element at the i index.

69
00:04:08,320 --> 00:04:11,920
Once we've completed that and
iterated over the whole list,

70
00:04:11,920 --> 00:04:16,450
we have a sorted array, where
we have the minimum values being

71
00:04:16,450 --> 00:04:19,240
selected to go to the beginning.

72
00:04:19,240 --> 00:04:22,660
That was selection sort, where
we take the minimum values

73
00:04:22,660 --> 00:04:24,340
and we move them to the beginning.

74
00:04:24,340 --> 00:04:27,130
Now, bubble sort will actually
take the largest elements

75
00:04:27,130 --> 00:04:29,470
and bubble them to the end.

76
00:04:29,470 --> 00:04:34,060
Bubble sort will iterate over our
array, comparing adjacent elements.

77
00:04:34,060 --> 00:04:36,220
Every time a comparison
is made, we're going

78
00:04:36,220 --> 00:04:39,590
to swap any elements that
are in the wrong order.

79
00:04:39,590 --> 00:04:45,370
And once we don't make any swaps,
then that means the list is sorted.

80
00:04:45,370 --> 00:04:49,780
Let's look at the very same array,
but now apply a bubble sort.

81
00:04:49,780 --> 00:04:52,840
I'm going to start by looking
at the first two elements

82
00:04:52,840 --> 00:04:55,290
at index 0 and index 1.

83
00:04:55,290 --> 00:05:00,310
3 is less than 5, so as of
now, the array is in order.

84
00:05:00,310 --> 00:05:02,680
I increment both my
left and right indices,

85
00:05:02,680 --> 00:05:07,960
and I find that 5 is greater than
2, and so I swap those two values.

86
00:05:07,960 --> 00:05:13,270
Incrementing my indices again, 5 is
greater than 1, so that gets swapped.

87
00:05:13,270 --> 00:05:17,350
Incrementing again, 5 is greater
than 4, so that gets swapped.

88
00:05:17,350 --> 00:05:23,210
So you'll see here how 5
bubbled all the way to the end.

89
00:05:23,210 --> 00:05:25,300
I can lock that in now.

90
00:05:25,300 --> 00:05:26,740
I go back to the beginning.

91
00:05:26,740 --> 00:05:29,950
Compare the values at 0 and at 1.

92
00:05:29,950 --> 00:05:31,820
3 is larger than 2.

93
00:05:31,820 --> 00:05:33,250
So that gets swapped.

94
00:05:33,250 --> 00:05:34,580
3 is larger than 1.

95
00:05:34,580 --> 00:05:35,980
So that gets swapped.

96
00:05:35,980 --> 00:05:38,680
Now, 3 is not larger than 4.

97
00:05:38,680 --> 00:05:40,930
And so I don't make any swaps.

98
00:05:40,930 --> 00:05:45,640
So I can then lock in the value 4.

99
00:05:45,640 --> 00:05:47,050
I go back to the beginning.

100
00:05:47,050 --> 00:05:48,580
2 is greater than 1.

101
00:05:48,580 --> 00:05:49,870
I swap those.

102
00:05:49,870 --> 00:05:52,180
2 is not greater than 3.

103
00:05:52,180 --> 00:05:54,970
I don't swap, and I lock that in.

104
00:05:54,970 --> 00:05:58,570
Comparing once more, 1 is less than 2.

105
00:05:58,570 --> 00:06:00,490
So no swaps are made.

106
00:06:00,490 --> 00:06:04,170
And thus, I have sorted my list.

107
00:06:04,170 --> 00:06:06,690
And there we have a sorted array.

108
00:06:06,690 --> 00:06:07,700
My name is Zamyla.

109
00:06:07,700 --> 00:06:10,610
And this was sort.

110
00:06:10,610 --> 00:06:12,122