1
00:00:00,000 --> 00:00:05,726
>> [MUSIC PLAYING]

2
00:00:05,726 --> 00:00:08,600
DOUG LLOYD: Selection sort is an
algorithm that, as you might expect,

3
00:00:08,600 --> 00:00:10,470
sorts a set of elements.

4
00:00:10,470 --> 00:00:12,470
And algorithm recall
is a step-by-step set

5
00:00:12,470 --> 00:00:15,260
of instructions for completing a task.

6
00:00:15,260 --> 00:00:17,580
>> In selection sort the
basic idea is this,

7
00:00:17,580 --> 00:00:22,080
find the smallest unsorted element and
add it to the end of the sorted list.

8
00:00:22,080 --> 00:00:26,970
Effectively what this does is build
a sorted list, one element at a time.

9
00:00:26,970 --> 00:00:29,800
Breaking it down to pseudocode
we could state this algorithm

10
00:00:29,800 --> 00:00:34,490
as follows, repeat this until
no unsorted elements remain.

11
00:00:34,490 --> 00:00:38,660
Search through the unsorted
data to find the smallest value,

12
00:00:38,660 --> 00:00:44,130
then swap the smallest value with the
first element of the unsorted part.

13
00:00:44,130 --> 00:00:47,130
>> It may help to visualize this,
so let's take a look at this.

14
00:00:47,130 --> 00:00:49,710
So this, I contend, is an
unsorted array and I've

15
00:00:49,710 --> 00:00:53,040
indicated it by indicating that all
of the elements are colored red,

16
00:00:53,040 --> 00:00:54,420
they are not yet sorted.

17
00:00:54,420 --> 00:00:57,670
This is the entire
unsorted part of the array.

18
00:00:57,670 --> 00:01:02,020
>> So let's go through the steps of
selection sort to sort this array.

19
00:01:02,020 --> 00:01:05,296
So again, we're gonna repeat
until no unsorted elements remain.

20
00:01:05,296 --> 00:01:07,920
We're gonna search through the
data to find the smallest value,

21
00:01:07,920 --> 00:01:11,990
and then swap that value with the
first element of the unsorted part.

22
00:01:11,990 --> 00:01:14,380
>> Right now, again, the entire
array is the unsorted part.

23
00:01:14,380 --> 00:01:16,534
All of the red elements are unsorted.

24
00:01:16,534 --> 00:01:18,700
So we search through and
we find the smallest value.

25
00:01:18,700 --> 00:01:20,533
We start at the beginning,
we go to the end,

26
00:01:20,533 --> 00:01:23,630
we find the smallest value is, one.

27
00:01:23,630 --> 00:01:24,860
So that's part one.

28
00:01:24,860 --> 00:01:29,440
And then part two, swap that value with
the first element of the unsorted part,

29
00:01:29,440 --> 00:01:31,340
or the first red element.

30
00:01:31,340 --> 00:01:34,980
>> In this case that would be
five, so we swap one and five.

31
00:01:34,980 --> 00:01:37,320
When we do this, we can
visually see that we've

32
00:01:37,320 --> 00:01:41,260
moved the smallest valued element
of the array, to the very beginning.

33
00:01:41,260 --> 00:01:43,920
Effectively sorting that element.

34
00:01:43,920 --> 00:01:47,520
>> And so we can indeed confirm
and state that one, is sorted.

35
00:01:47,520 --> 00:01:52,080
And so we'll indicate the sorted portion
of our array, by coloring it blue.

36
00:01:52,080 --> 00:01:53,860
>> Now we just repeat the process again.

37
00:01:53,860 --> 00:01:57,430
We search through the unsorted part of
the array to find the smallest element.

38
00:01:57,430 --> 00:01:59,000
In this case, it's two.

39
00:01:59,000 --> 00:02:02,100
>> We swap that with the first
element of the unsorted part.

40
00:02:02,100 --> 00:02:05,540
In this case two also happens to be
the first element of the unsorted part.

41
00:02:05,540 --> 00:02:08,650
So we swap two with itself,
which really just leaves two

42
00:02:08,650 --> 00:02:11,257
where it is, and it's sorted.

43
00:02:11,257 --> 00:02:13,840
Continuing on, we search through
to find the smallest element.

44
00:02:13,840 --> 00:02:15,030
It's three.

45
00:02:15,030 --> 00:02:17,650
We swap it with the first
element, which is five.

46
00:02:17,650 --> 00:02:19,450
And now three is sorted.

47
00:02:19,450 --> 00:02:22,440
>> We search through again, and we
find the smallest element is four.

48
00:02:22,440 --> 00:02:28,070
We swap it with the first element of the
unsorted part, and now four is sorted.

49
00:02:28,070 --> 00:02:29,910
>> We find that five is
the smallest element.

50
00:02:29,910 --> 00:02:32,900
We swap it with the first
element of the unsorted part.

51
00:02:32,900 --> 00:02:34,740
And now five is sorted.

52
00:02:34,740 --> 00:02:36,660
>> And then lastly, our
unsorted part consists

53
00:02:36,660 --> 00:02:38,576
of just a single element,
so we search through

54
00:02:38,576 --> 00:02:41,740
and we find that six is the
smallest, and in fact, only element.

55
00:02:41,740 --> 00:02:44,906
And then we can state that it is sorted.

56
00:02:44,906 --> 00:02:47,530
And now we've switched our array
from being completely unsorted

57
00:02:47,530 --> 00:02:52,660
in red, to completely sorted
in blue, using selection sort.

58
00:02:52,660 --> 00:02:54,920
>> So what's the worst case scenario here?

59
00:02:54,920 --> 00:02:57,830
Well in the absolute worst
case, we have to look over

60
00:02:57,830 --> 00:03:02,170
all of the elements of the array to
find the smallest unsorted element,

61
00:03:02,170 --> 00:03:04,750
and we have to repeat
this process n times.

62
00:03:04,750 --> 00:03:09,090
Once for each element of the array
because we only, in this algorithm,

63
00:03:09,090 --> 00:03:12,180
sort one element at time.

64
00:03:12,180 --> 00:03:13,595
>> What's the best case scenario?

65
00:03:13,595 --> 00:03:15,040
Well it's exactly the same, right?

66
00:03:15,040 --> 00:03:18,440
We actually have to still step through
every single element of the array

67
00:03:18,440 --> 00:03:22,040
in order to confirm that it is,
in fact, the smallest element.

68
00:03:22,040 --> 00:03:26,760
>> So the worst case runtime, we
have to repeat a process n times,

69
00:03:26,760 --> 00:03:28,960
once for each of n elements.

70
00:03:28,960 --> 00:03:31,940
And in the best case scenario,
we have to do the same.

71
00:03:31,940 --> 00:03:35,340
>> So thinking back to our
computational complexity toolbox,

72
00:03:35,340 --> 00:03:39,250
what do you think is the worst
case runtime for selection sort?

73
00:03:39,250 --> 00:03:41,840
What do you think is the best
case runtime for selection sort?

74
00:03:41,840 --> 00:03:44,760

75
00:03:44,760 --> 00:03:49,325
>> Did you guess Big O of n squared,
and Big Omega of n squared?

76
00:03:49,325 --> 00:03:49,950
You'd be right.

77
00:03:49,950 --> 00:03:52,490
Those are, in fact, the
worst case and best case run

78
00:03:52,490 --> 00:03:55,100
times, for selection sort.

79
00:03:55,100 --> 00:03:56,260
>> I'm Doug Lloyd.

80
00:03:56,260 --> 00:03:58,600
This is CS50.

81
00:03:58,600 --> 00:04:00,279