1
00:00:00,480 --> 00:00:04,080
‫So now we're going to write our code for insertion sort.

2
00:00:04,410 --> 00:00:10,200
‫We'll pick up where we left off in the last video with these two items swapped.

3
00:00:10,440 --> 00:00:14,610
‫And I'll shrink this down to the bottom here to make room for our code.

4
00:00:14,790 --> 00:00:20,040
‫We'll pass it the array and the size, and we'll start out with our for loop.

5
00:00:20,070 --> 00:00:23,670
‫Notice that I is equal to one.

6
00:00:23,670 --> 00:00:29,730
‫Normally we start at the beginning of the array at zero, but we're starting at this second item and

7
00:00:29,730 --> 00:00:32,070
‫comparing it to the item before.

8
00:00:32,670 --> 00:00:40,590
‫And we're going to set a variable temp to be equal to the value of that item at the index of AI.

9
00:00:41,010 --> 00:00:45,270
‫And we're going to create a variable J that points to the previous item.

10
00:00:45,270 --> 00:00:46,690
‫We'll do that like this.

11
00:00:46,710 --> 00:00:49,770
‫J equals I minus one.

12
00:00:50,160 --> 00:00:58,110
‫So we'll put that two back here and we're going to jump forward to this item because this is the first

13
00:00:58,110 --> 00:01:00,870
‫value that we need to move.

14
00:01:01,320 --> 00:01:06,030
‫This will be I and our for loop and this will be J.

15
00:01:07,000 --> 00:01:14,410
‫And we'll say while temp is less than a ray at the index of J, that is this item.

16
00:01:14,890 --> 00:01:17,380
‫And remember this will be temp.

17
00:01:17,500 --> 00:01:22,330
‫So this conditional will be true for this iteration of the wild loop.

18
00:01:23,150 --> 00:01:31,040
‫We'll set a ray at the index of J plus one to be equal to a ray at the index of J.

19
00:01:31,340 --> 00:01:34,970
‫So that puts the value of four in that spot.

20
00:01:35,330 --> 00:01:41,450
‫Then we need to put the value of three into this spot, and we'll do that like this.

21
00:01:41,450 --> 00:01:49,670
‫A ray at the index of j equals temp and then we need to decrement J to move that over and we'll do that

22
00:01:49,670 --> 00:01:50,390
‫like this.

23
00:01:50,390 --> 00:01:51,980
‫J Minus, minus.

24
00:01:52,460 --> 00:01:55,220
‫Now we'll run the while loop again.

25
00:01:55,220 --> 00:02:00,410
‫And now temp is not less than a ray at the index of J.

26
00:02:00,770 --> 00:02:06,620
‫So that breaks us out of this while loop and that three stays at that index.

27
00:02:07,070 --> 00:02:11,600
‫So this code will almost work for insertion sort.

28
00:02:11,720 --> 00:02:15,020
‫But there is an edge case that we need to address.

29
00:02:15,380 --> 00:02:21,080
‫And to illustrate this, I'm going to take the first two items in the array and I'm going to switch

30
00:02:21,080 --> 00:02:21,530
‫them.

31
00:02:22,070 --> 00:02:29,480
‫So now we're going to take this second item and compare it to the item before it j will be set equal

32
00:02:29,480 --> 00:02:31,040
‫to this index.

33
00:02:31,520 --> 00:02:34,190
‫And then we'll go into the while loop.

34
00:02:34,820 --> 00:02:43,040
‫We'll say while temp is less than a ray at the index of J and it is the case here we'll set a ray at

35
00:02:43,040 --> 00:02:49,880
‫the index of J plus one to be equal to a ray at the index of J, which does this.

36
00:02:50,150 --> 00:02:56,960
‫We'll set a ray at the index of J to be equal to temp, which puts this one in this spot.

37
00:02:57,260 --> 00:03:01,280
‫But the problem arises with this line of code.

38
00:03:01,430 --> 00:03:07,880
‫When we say J minus minus J is now pointing to the index of negative one.

39
00:03:08,090 --> 00:03:15,740
‫And obviously we can't have an index of negative one in an array, so we have to add something to our

40
00:03:15,740 --> 00:03:16,700
‫while loop.

41
00:03:17,360 --> 00:03:26,390
‫J also needs to be greater than negative one, so both of these conditions need to be true.

42
00:03:26,780 --> 00:03:33,500
‫Now, one of the things that is very important is the order in which you write this in the while loop.

43
00:03:33,980 --> 00:03:41,210
‫If you write it like this, this test will happen first and you will be looking for an index of negative

44
00:03:41,210 --> 00:03:44,360
‫one and you're going to get an error.

45
00:03:44,840 --> 00:03:48,230
‫So you have to write it in this order.

46
00:03:48,680 --> 00:03:57,980
‫So now that breaks us out of our while loop and that one stays at that index and now our array is sorted.

47
00:03:58,490 --> 00:04:01,940
‫So that is all of our code for insertion sort.

48
00:04:01,970 --> 00:04:05,000
‫We'll look at this code in a moment in VTS code.

49
00:04:05,270 --> 00:04:12,230
‫And when we do we'll start out with an array that looks like this and then we'll run insertion sort

50
00:04:12,350 --> 00:04:13,790
‫and we will sort that.

51
00:04:14,520 --> 00:04:17,730
‫So now let's flip over and take a look at this.

52
00:04:18,870 --> 00:04:21,930
‫So there is our function for insertion sort.

53
00:04:22,320 --> 00:04:29,790
‫And I'll scroll up and in our main function this creates that array that we just saw and this calculates

54
00:04:29,790 --> 00:04:30,930
‫the size.

55
00:04:31,170 --> 00:04:36,060
‫And with this line, we'll run insertion, sort on the array with the size.

56
00:04:36,060 --> 00:04:40,110
‫And this for loop will print out the sorted array.

57
00:04:40,530 --> 00:04:41,940
‫So I'll run this.

58
00:04:42,590 --> 00:04:46,040
‫And we have a sorted array one through six.

59
00:04:46,860 --> 00:04:51,000
‫So that is our function for insertion sort.