WEBVTT X-TIMESTAMP-MAP=LOCAL:00:00:00.000,MPEGTS:900000 00:00:00.000 --> 00:00:05.726 >> [MUSIC PLAYING] 00:00:05.726 --> 00:00:08.600 DOUG LLOYD: Selection sort is an algorithm that, as you might expect, 00:00:08.600 --> 00:00:10.470 sorts a set of elements. 00:00:10.470 --> 00:00:12.470 And algorithm recall is a step-by-step set 00:00:12.470 --> 00:00:15.260 of instructions for completing a task. 00:00:15.260 --> 00:00:17.580 >> In selection sort the basic idea is this, 00:00:17.580 --> 00:00:22.080 find the smallest unsorted element and add it to the end of the sorted list. 00:00:22.080 --> 00:00:26.970 Effectively what this does is build a sorted list, one element at a time. 00:00:26.970 --> 00:00:29.800 Breaking it down to pseudocode we could state this algorithm 00:00:29.800 --> 00:00:34.490 as follows, repeat this until no unsorted elements remain. 00:00:34.490 --> 00:00:38.660 Search through the unsorted data to find the smallest value, 00:00:38.660 --> 00:00:44.130 then swap the smallest value with the first element of the unsorted part. 00:00:44.130 --> 00:00:47.130 >> It may help to visualize this, so let's take a look at this. 00:00:47.130 --> 00:00:49.710 So this, I contend, is an unsorted array and I've 00:00:49.710 --> 00:00:53.040 indicated it by indicating that all of the elements are colored red, 00:00:53.040 --> 00:00:54.420 they are not yet sorted. 00:00:54.420 --> 00:00:57.670 This is the entire unsorted part of the array. 00:00:57.670 --> 00:01:02.020 >> So let's go through the steps of selection sort to sort this array. 00:01:02.020 --> 00:01:05.296 So again, we're gonna repeat until no unsorted elements remain. 00:01:05.296 --> 00:01:07.920 We're gonna search through the data to find the smallest value, 00:01:07.920 --> 00:01:11.990 and then swap that value with the first element of the unsorted part. 00:01:11.990 --> 00:01:14.380 >> Right now, again, the entire array is the unsorted part. 00:01:14.380 --> 00:01:16.534 All of the red elements are unsorted. 00:01:16.534 --> 00:01:18.700 So we search through and we find the smallest value. 00:01:18.700 --> 00:01:20.533 We start at the beginning, we go to the end, 00:01:20.533 --> 00:01:23.630 we find the smallest value is, one. 00:01:23.630 --> 00:01:24.860 So that's part one. 00:01:24.860 --> 00:01:29.440 And then part two, swap that value with the first element of the unsorted part, 00:01:29.440 --> 00:01:31.340 or the first red element. 00:01:31.340 --> 00:01:34.980 >> In this case that would be five, so we swap one and five. 00:01:34.980 --> 00:01:37.320 When we do this, we can visually see that we've 00:01:37.320 --> 00:01:41.260 moved the smallest valued element of the array, to the very beginning. 00:01:41.260 --> 00:01:43.920 Effectively sorting that element. 00:01:43.920 --> 00:01:47.520 >> And so we can indeed confirm and state that one, is sorted. 00:01:47.520 --> 00:01:52.080 And so we'll indicate the sorted portion of our array, by coloring it blue. 00:01:52.080 --> 00:01:53.860 >> Now we just repeat the process again. 00:01:53.860 --> 00:01:57.430 We search through the unsorted part of the array to find the smallest element. 00:01:57.430 --> 00:01:59.000 In this case, it's two. 00:01:59.000 --> 00:02:02.100 >> We swap that with the first element of the unsorted part. 00:02:02.100 --> 00:02:05.540 In this case two also happens to be the first element of the unsorted part. 00:02:05.540 --> 00:02:08.650 So we swap two with itself, which really just leaves two 00:02:08.650 --> 00:02:11.257 where it is, and it's sorted. 00:02:11.257 --> 00:02:13.840 Continuing on, we search through to find the smallest element. 00:02:13.840 --> 00:02:15.030 It's three. 00:02:15.030 --> 00:02:17.650 We swap it with the first element, which is five. 00:02:17.650 --> 00:02:19.450 And now three is sorted. 00:02:19.450 --> 00:02:22.440 >> We search through again, and we find the smallest element is four. 00:02:22.440 --> 00:02:28.070 We swap it with the first element of the unsorted part, and now four is sorted. 00:02:28.070 --> 00:02:29.910 >> We find that five is the smallest element. 00:02:29.910 --> 00:02:32.900 We swap it with the first element of the unsorted part. 00:02:32.900 --> 00:02:34.740 And now five is sorted. 00:02:34.740 --> 00:02:36.660 >> And then lastly, our unsorted part consists 00:02:36.660 --> 00:02:38.576 of just a single element, so we search through 00:02:38.576 --> 00:02:41.740 and we find that six is the smallest, and in fact, only element. 00:02:41.740 --> 00:02:44.906 And then we can state that it is sorted. 00:02:44.906 --> 00:02:47.530 And now we've switched our array from being completely unsorted 00:02:47.530 --> 00:02:52.660 in red, to completely sorted in blue, using selection sort. 00:02:52.660 --> 00:02:54.920 >> So what's the worst case scenario here? 00:02:54.920 --> 00:02:57.830 Well in the absolute worst case, we have to look over 00:02:57.830 --> 00:03:02.170 all of the elements of the array to find the smallest unsorted element, 00:03:02.170 --> 00:03:04.750 and we have to repeat this process n times. 00:03:04.750 --> 00:03:09.090 Once for each element of the array because we only, in this algorithm, 00:03:09.090 --> 00:03:12.180 sort one element at time. 00:03:12.180 --> 00:03:13.595 >> What's the best case scenario? 00:03:13.595 --> 00:03:15.040 Well it's exactly the same, right? 00:03:15.040 --> 00:03:18.440 We actually have to still step through every single element of the array 00:03:18.440 --> 00:03:22.040 in order to confirm that it is, in fact, the smallest element. 00:03:22.040 --> 00:03:26.760 >> So the worst case runtime, we have to repeat a process n times, 00:03:26.760 --> 00:03:28.960 once for each of n elements. 00:03:28.960 --> 00:03:31.940 And in the best case scenario, we have to do the same. 00:03:31.940 --> 00:03:35.340 >> So thinking back to our computational complexity toolbox, 00:03:35.340 --> 00:03:39.250 what do you think is the worst case runtime for selection sort? 00:03:39.250 --> 00:03:41.840 What do you think is the best case runtime for selection sort? 00:03:44.760 --> 00:03:49.325 >> Did you guess Big O of n squared, and Big Omega of n squared? 00:03:49.325 --> 00:03:49.950 You'd be right. 00:03:49.950 --> 00:03:52.490 Those are, in fact, the worst case and best case run 00:03:52.490 --> 00:03:55.100 times, for selection sort. 00:03:55.100 --> 00:03:56.260 >> I'm Doug Lloyd. 00:03:56.260 --> 00:03:58.600 This is CS50.