1 00:00:00,000 --> 00:00:02,826 [MUSIC PLAYING] 2 00:00:02,826 --> 00:00:05,660 3 00:00:05,660 --> 00:00:09,370 DOUG LLOYD: So insertion sort is another algorithm we can use to sort an array. 4 00:00:09,370 --> 00:00:12,350 The idea behind this algorithm is to build your sorted array 5 00:00:12,350 --> 00:00:19,670 in place, shifting elements out of the way as you go, to make room. 6 00:00:19,670 --> 00:00:22,240 This is slightly different from selection sort or bubble 7 00:00:22,240 --> 00:00:25,460 sort, for example, where we're adjusting the locations, 8 00:00:25,460 --> 00:00:26,910 where we're making swaps. 9 00:00:26,910 --> 00:00:29,760 In this case what we're actually doing is sliding elements 10 00:00:29,760 --> 00:00:31,390 over, out of the way. 11 00:00:31,390 --> 00:00:34,030 How does this algorithm work in pseudocode? 12 00:00:34,030 --> 00:00:37,646 Well let's just arbitrarily say that the first element of the array is sorted. 13 00:00:37,646 --> 00:00:38,770 We're building it in place. 14 00:00:38,770 --> 00:00:42,660 We're gonna go one element at a time and build it, and so the first thing we see 15 00:00:42,660 --> 00:00:43,890 is a one element array. 16 00:00:43,890 --> 00:00:47,720 And by definition, a one element array is sorted. 17 00:00:47,720 --> 00:00:50,850 Then we'll repeat this process until-- we'll repeat the following process 18 00:00:50,850 --> 00:00:52,900 until all of the elements are sorted. 19 00:00:52,900 --> 00:00:57,770 Look at the next unsorted element and insert it into the sorted portion, 20 00:00:57,770 --> 00:01:01,209 by shifting the required number of elements out of the way. 21 00:01:01,209 --> 00:01:03,750 Hopefully this visualization will help you see exactly what's 22 00:01:03,750 --> 00:01:05,980 going on with insertion sort. 23 00:01:05,980 --> 00:01:08,010 So again, here's our entire unsorted array, 24 00:01:08,010 --> 00:01:10,970 all of the elements indicated in red. 25 00:01:10,970 --> 00:01:13,320 And let's follow the steps of our pseudocode. 26 00:01:13,320 --> 00:01:16,970 The first thing we do, is we call the first element of the array, sorted. 27 00:01:16,970 --> 00:01:20,920 So we're just gonna say five, you're now sorted. 28 00:01:20,920 --> 00:01:24,570 Then we look at the next unsorted element of the array 29 00:01:24,570 --> 00:01:27,610 and we want to insert that into the sorted portion, 30 00:01:27,610 --> 00:01:29,750 by shifting elements over. 31 00:01:29,750 --> 00:01:33,470 So two is the next unsorted element of the array. 32 00:01:33,470 --> 00:01:36,250 Clearly it belongs before the five, so what we're gonna do 33 00:01:36,250 --> 00:01:41,580 is sort of hold two aside for a second, shift five over, and then insert two 34 00:01:41,580 --> 00:01:43,210 before five, where to should go. 35 00:01:43,210 --> 00:01:45,280 And now we can say that two is sorted. 36 00:01:45,280 --> 00:01:48,400 So as you can see, we've only so far looked at two elements of the array. 37 00:01:48,400 --> 00:01:50,600 We haven't looked at the rest at all, but we've 38 00:01:50,600 --> 00:01:54,582 got those two elements sorted by way of the shifting mechanism. 39 00:01:54,582 --> 00:01:56,410 So we repeat the process again. 40 00:01:56,410 --> 00:01:58,850 Look at the next unsorted element, that's one. 41 00:01:58,850 --> 00:02:04,010 Let's hold that aside for a second, shift everything over, and put one 42 00:02:04,010 --> 00:02:05,570 where it should go. 43 00:02:05,570 --> 00:02:08,110 Again, still, we've only ever looked at one, two, and five. 44 00:02:08,110 --> 00:02:12,480 We don't know what else is coming, but we've sorted those three elements. 45 00:02:12,480 --> 00:02:16,030 Next unsorted element is three, so we'll set it aside. 46 00:02:16,030 --> 00:02:18,200 We'll shift over what we need to which, this time 47 00:02:18,200 --> 00:02:21,820 is not everything as in the previous two cases, it's just the five. 48 00:02:21,820 --> 00:02:25,440 And then we'll stick three in, between the two and the five. 49 00:02:25,440 --> 00:02:27,849 Six is the next unsorted element to the array. 50 00:02:27,849 --> 00:02:31,140 And in fact six is greater than five, so we don't even need to do any swapping. 51 00:02:31,140 --> 00:02:35,710 We can just tack six right on to the end of the sorted portion. 52 00:02:35,710 --> 00:02:38,270 Lastly, four is the last unsorted element. 53 00:02:38,270 --> 00:02:42,060 So we'll set it aside, shift over the elements we need to shift over, 54 00:02:42,060 --> 00:02:43,780 and then put four where it belongs. 55 00:02:43,780 --> 00:02:46,400 And now look, we've sort of all the elements. 56 00:02:46,400 --> 00:02:48,150 Notice with insertion sort, we didn't have 57 00:02:48,150 --> 00:02:50,240 to go back and forth across the array. 58 00:02:50,240 --> 00:02:54,720 We only went across the array one time, and we shifted things 59 00:02:54,720 --> 00:02:59,870 that we'd already encountered, in order to make room for the new elements. 60 00:02:59,870 --> 00:03:02,820 So what's the worst case scenario with insertion sort? 61 00:03:02,820 --> 00:03:05,090 In the worst case, the array is in reverse order. 62 00:03:05,090 --> 00:03:11,180 You have to shift each of the n elements up to n positions, every single time we 63 00:03:11,180 --> 00:03:12,880 make an insertion. 64 00:03:12,880 --> 00:03:15,720 That's a lot of shifting. 65 00:03:15,720 --> 00:03:18,014 In the best case, the array is perfectly sorted. 66 00:03:18,014 --> 00:03:20,680 And sort of like what happened with five and six in the example, 67 00:03:20,680 --> 00:03:23,779 where we could just tack it on without having to do any shifting, 68 00:03:23,779 --> 00:03:24,820 we'd essentially do that. 69 00:03:24,820 --> 00:03:27,560 If you imagine that our array was one through six, 70 00:03:27,560 --> 00:03:29,900 we'd start off by declaring one is sorted. 71 00:03:29,900 --> 00:03:33,300 Two comes after one so we can just say, OK, well one and two are sorted. 72 00:03:33,300 --> 00:03:36,190 Three comes after two so, OK, one and two and three are sorted. 73 00:03:36,190 --> 00:03:39,590 We're not making any swaps, we're just moving this arbitrary line 74 00:03:39,590 --> 00:03:42,460 between sorted and unsorted as we go. 75 00:03:42,460 --> 00:03:46,646 As effectively as we did in the example, turning elements blue, as we proceed. 76 00:03:46,646 --> 00:03:48,270 So what's the worst case runtime, then? 77 00:03:48,270 --> 00:03:51,854 Remember, if we have to shift each of the n elements possibly n positions, 78 00:03:51,854 --> 00:03:54,020 hopefully that gives you an idea that the worst case 79 00:03:54,020 --> 00:03:57,770 runtime is Big O of n squared. 80 00:03:57,770 --> 00:04:00,220 If the array is perfectly sorted, all we have to do 81 00:04:00,220 --> 00:04:04,480 is look at every single element once, and then we're done. 82 00:04:04,480 --> 00:04:08,440 So in the best case, it's omega of n. 83 00:04:08,440 --> 00:04:09,490 I'm Doug Lloyd. 84 00:04:09,490 --> 00:04:11,760 This is CS50. 85 00:04:11,760 --> 00:04:13,119