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