1
00:00:07,090 --> 00:00:09,940
Now that we have a good understanding of.

2
00:00:11,130 --> 00:00:13,700
Sorting algorithm like selection sort.

3
00:00:13,710 --> 00:00:17,610
We can continue on and learn additional sorting algorithms.

4
00:00:17,760 --> 00:00:22,710
In this lecture, we are going to begin looking at what bubble sort is.

5
00:00:23,250 --> 00:00:30,480
And bubble sort is one of the simplest sorting algorithms because it just repeatedly swaps the adjacent

6
00:00:30,480 --> 00:00:32,940
values if they are in the wrong order.

7
00:00:33,240 --> 00:00:41,070
So it's not going to be super performant for large data sets, but it's still a good sorting sorting

8
00:00:41,070 --> 00:00:45,030
algorithm that we can evaluate and learn.

9
00:00:45,660 --> 00:00:54,600
So we'll create ourselves an array here and we'll give it five, four, one, three and two.

10
00:00:58,060 --> 00:01:03,190
And remember, what we're going to do is sort adjacent values.

11
00:01:04,110 --> 00:01:05,730
If they are in the wrong order.

12
00:01:06,390 --> 00:01:08,310
So we see here.

13
00:01:08,310 --> 00:01:13,800
So we'll start at five and zero and we see that our adjacent value is four.

14
00:01:13,800 --> 00:01:19,260
So now we can swap five and four and then leave the rest of them the same.

15
00:01:22,200 --> 00:01:27,550
And we're still on value five because we have not iterated through the entire array.

16
00:01:27,570 --> 00:01:34,630
So now we're still at five and we're going to swap now with value one because one is less than five.

17
00:01:34,650 --> 00:01:40,140
So now our array is 415, three, two.

18
00:01:45,780 --> 00:01:51,820
And again, since we haven't completely iterated through the array yet, we are still on value five.

19
00:01:51,840 --> 00:01:54,630
So now we will compare five and three.

20
00:01:54,960 --> 00:01:57,400
Three is less than five.

21
00:01:57,420 --> 00:01:59,780
So now we will swap three and five.

22
00:01:59,790 --> 00:02:03,570
So now we have four one, three, five, two.

23
00:02:06,660 --> 00:02:11,700
And now that we're almost at the end of the array, we have one more check that we need to do.

24
00:02:11,760 --> 00:02:16,350
And we need to check if five is less than two, which it is.

25
00:02:16,350 --> 00:02:21,540
So now we have four one, three, two and five.

26
00:02:25,670 --> 00:02:28,530
So now we have completely iterated five through the array.

27
00:02:28,550 --> 00:02:32,600
So now we know that index five is in the correct spot.

28
00:02:33,230 --> 00:02:40,760
Five is in correct spot.

29
00:02:42,370 --> 00:02:46,060
So now we're going to go back and we're going to start over with four.

30
00:02:46,300 --> 00:02:50,940
So now we're here at four and we're going to compare it to one.

31
00:02:50,950 --> 00:02:53,150
So we know that one is less than four.

32
00:02:53,170 --> 00:02:55,660
So now we go one for three.

33
00:02:57,240 --> 00:02:58,560
Two and five.

34
00:03:03,340 --> 00:03:04,510
We're still at four.

35
00:03:04,840 --> 00:03:06,870
So now we compare four and three.

36
00:03:06,880 --> 00:03:10,810
So we have one, three, 4 to 5.

37
00:03:12,130 --> 00:03:20,500
So you're starting to see why this algorithm might not be the most efficient one of all the sorting

38
00:03:20,500 --> 00:03:25,450
algorithms that we will learn.

39
00:03:26,380 --> 00:03:28,030
So we're still at four.

40
00:03:28,960 --> 00:03:30,490
So four is less than two.

41
00:03:30,520 --> 00:03:35,860
So one, three, two, four, five.

42
00:03:37,210 --> 00:03:38,320
We see that.

43
00:03:38,320 --> 00:03:42,220
We know that five is in the correct order already, so now we're done with four.

44
00:03:42,250 --> 00:03:47,450
So now you're quickly starting to see the pattern here.

45
00:03:47,470 --> 00:03:52,700
So our next value is one, we compare 1 to 3, two, four and five.

46
00:03:52,720 --> 00:03:55,600
So now we know that one is in the correct spot.

47
00:03:55,780 --> 00:03:58,930
So now we compare three and two.

48
00:04:00,720 --> 00:04:06,810
So we know that we need to go one, two, three, four and five.

49
00:04:07,230 --> 00:04:09,930
And now we have our sorted array.

50
00:04:10,230 --> 00:04:13,800
So we are now done with sorting this array.

51
00:04:15,420 --> 00:04:24,540
So again, now you can see why it is not the most efficient algorithm, but let's look at some pseudocode

52
00:04:24,570 --> 00:04:28,110
to see what it would look like, not a B.

53
00:04:29,370 --> 00:04:32,170
So we want some pseudocode.

54
00:04:32,190 --> 00:04:39,000
That way we can have a blueprint for what we want to code when we go to do our implementation.

55
00:04:39,300 --> 00:04:46,930
So we know that we started at iteration one, so this would be one for loop.

56
00:04:46,950 --> 00:04:58,260
So we'll say for AI to excuse me for AI in zero.

57
00:04:59,770 --> 00:05:03,610
To size minus one.

58
00:05:04,210 --> 00:05:11,290
And then we're comparing it with all the elements adjacent to it.

59
00:05:12,520 --> 00:05:14,950
So we're going to need another four loop.

60
00:05:14,950 --> 00:05:19,060
So we'll say four j in.

61
00:05:23,420 --> 00:05:25,880
One, two.

62
00:05:26,210 --> 00:05:29,300
Size minus two.

63
00:05:31,800 --> 00:05:33,900
And then we will do our compare.

64
00:05:37,840 --> 00:05:38,470
J.

65
00:05:40,680 --> 00:05:54,930
I compare J If it is greater than J plus one, and if it is, then we want to swap J and J plus one,

66
00:05:56,280 --> 00:05:59,310
and that is basically our pseudocode for this.

67
00:05:59,310 --> 00:06:01,020
So let's do one more example.

68
00:06:01,020 --> 00:06:06,060
That way we make sure that we have a good understanding of how this algorithm works now that we kind

69
00:06:06,060 --> 00:06:07,740
of know what the pseudocode is.

70
00:06:09,230 --> 00:06:10,760
So we will do.

71
00:06:12,080 --> 00:06:19,400
An array of values of five, one, four, two and eight.

72
00:06:20,030 --> 00:06:25,280
So this is our unsorted vector of values.

73
00:06:25,280 --> 00:06:27,290
So we will start here.

74
00:06:29,830 --> 00:06:32,350
And then this will be our AI plus one.

75
00:06:32,650 --> 00:06:37,210
So now we we compare we see that we need to do a swap.

76
00:06:38,520 --> 00:06:40,830
Four, two and eight.

77
00:06:44,720 --> 00:06:47,350
So we're still here at five Compare.

78
00:06:47,360 --> 00:06:49,400
We need to do a swap now.

79
00:06:49,400 --> 00:06:50,180
We're one.

80
00:06:52,520 --> 00:06:56,540
Four, five, two and eight.

81
00:07:00,400 --> 00:07:01,780
So we're here still.

82
00:07:01,810 --> 00:07:06,460
Compare one four, two, five, eight.

83
00:07:06,940 --> 00:07:14,080
And now we know that five is in the correct spot because our next comparison will not yield a swap.

84
00:07:15,310 --> 00:07:18,210
So now we also know one is in the correct spot.

85
00:07:18,220 --> 00:07:29,320
So now we need to start here and we will evaluate two and four and we see one, two, four, five and

86
00:07:29,320 --> 00:07:29,770
eight.

87
00:07:30,160 --> 00:07:37,090
So that was a very simple one and we were able to quickly see how this works.

88
00:07:37,330 --> 00:07:44,560
It works really well with arrays that are already kind of sorted because as you can see, we had way

89
00:07:44,560 --> 00:07:50,380
less iterations needed here than we did in our array up here.

90
00:07:51,530 --> 00:07:58,310
So now that we have a really good understanding of how bubble sort works, let's go ahead and begin

91
00:07:58,310 --> 00:08:01,790
implementing this algorithm in the next lecture.