1
00:00:00,960 --> 00:00:01,830
Hi everyone.

2
00:00:01,830 --> 00:00:05,610
In this video let's discuss the logic of the bubble sort.

3
00:00:05,640 --> 00:00:10,590
Now let's say that we are given an array of integers seven, two, three, eight, one.

4
00:00:10,620 --> 00:00:17,490
Now initially the pointer would be placed at the beginning element of the given array, and we identify

5
00:00:17,490 --> 00:00:19,350
the element which is next to this.

6
00:00:19,350 --> 00:00:19,740
All right.

7
00:00:19,740 --> 00:00:23,070
So the indices over here 01234.

8
00:00:23,070 --> 00:00:25,470
So the pointer is at index zero.

9
00:00:25,470 --> 00:00:28,110
And the next element is at index one.

10
00:00:28,110 --> 00:00:31,770
Now we are going to check or compare these two values.

11
00:00:31,770 --> 00:00:34,380
And if needed we will swap them.

12
00:00:34,380 --> 00:00:36,900
Now seven and two is not in the ascending order right.

13
00:00:36,900 --> 00:00:38,040
Two is less than seven.

14
00:00:38,040 --> 00:00:39,270
So we need to swap them.

15
00:00:39,270 --> 00:00:41,250
So we will swap these two values.

16
00:00:41,250 --> 00:00:41,760
All right.

17
00:00:41,760 --> 00:00:45,810
So now at this point the pointer was at index zero.

18
00:00:45,810 --> 00:00:49,110
Now we got the array to 27381.

19
00:00:49,110 --> 00:00:52,740
Now again the indices are 01234.

20
00:00:52,860 --> 00:00:54,510
Now the pointer was at zero.

21
00:00:54,510 --> 00:00:57,780
Now we move the pointer to the next index which is one.

22
00:00:57,780 --> 00:01:01,140
And the value next to that is three.

23
00:01:01,140 --> 00:01:03,240
Now we are going to compare seven and three.

24
00:01:03,240 --> 00:01:04,740
Now they are not in order right.

25
00:01:04,740 --> 00:01:05,850
Three is less than seven.

26
00:01:05,850 --> 00:01:08,220
So we will swap them right.

27
00:01:08,220 --> 00:01:10,380
So we get 23781.

28
00:01:10,380 --> 00:01:14,580
And again we move this pointer to the next index which is at two.

29
00:01:14,580 --> 00:01:18,270
And we compare the value over here at at index two.

30
00:01:18,270 --> 00:01:19,110
Now we have seven.

31
00:01:19,110 --> 00:01:19,470
All right.

32
00:01:19,470 --> 00:01:21,150
So this was the previous array.

33
00:01:21,150 --> 00:01:22,860
Now we changed it again.

34
00:01:22,860 --> 00:01:24,420
We are looking at the indices.

35
00:01:25,490 --> 00:01:28,010
At this point the pointer was at index one.

36
00:01:28,010 --> 00:01:33,980
At this point the pointer is at index two, and we are comparing the values at index two and index three,

37
00:01:33,980 --> 00:01:34,880
seven and eight.

38
00:01:34,880 --> 00:01:35,990
They are in order.

39
00:01:35,990 --> 00:01:38,630
So we don't swap and we move the pointer.

40
00:01:38,630 --> 00:01:44,300
And we are going to compare the values at the indices three and four which is eight and one.

41
00:01:44,300 --> 00:01:45,740
And they are not in order.

42
00:01:45,740 --> 00:01:50,060
Therefore we will swap them and we get two, three, seven, one and eight.

43
00:01:50,060 --> 00:01:52,040
Now this is called one pass.

44
00:01:52,040 --> 00:01:54,920
So we have done n operations right.

45
00:01:54,920 --> 00:01:58,220
We have gone through the given array once.

46
00:01:58,220 --> 00:02:05,540
Now notice that after one pass the largest element is now at the right most place which is eight.

47
00:02:05,540 --> 00:02:08,330
So we don't need to shift this any longer.

48
00:02:08,330 --> 00:02:12,020
This now again this part of the array is still not sorted.

49
00:02:12,020 --> 00:02:12,380
Right.

50
00:02:12,380 --> 00:02:18,680
But this element which is the largest element is now at its right place, which is the right most place.

51
00:02:18,680 --> 00:02:20,870
Once we have sorted the array, it should be over here.

52
00:02:20,870 --> 00:02:21,260
Right.

53
00:02:21,260 --> 00:02:21,800
All right.

54
00:02:21,800 --> 00:02:23,780
So we are now over here.

55
00:02:23,780 --> 00:02:25,790
We have completed one pass.

56
00:02:26,300 --> 00:02:29,870
Now what we do is again we have our pointer over here.

57
00:02:29,870 --> 00:02:32,630
And we check that value with the next value.

58
00:02:32,630 --> 00:02:34,250
Now we keep doing this.

59
00:02:34,250 --> 00:02:40,700
But notice that we don't compare this value with the last position because as we already discussed,

60
00:02:40,700 --> 00:02:41,750
this is fixed.

61
00:02:41,750 --> 00:02:46,430
The position of value eight, which is the largest value, is already fixed.

62
00:02:46,430 --> 00:02:48,020
So we don't compare these two.

63
00:02:48,050 --> 00:02:49,460
So we stop at this point.

64
00:02:49,460 --> 00:02:49,790
All right.

65
00:02:49,790 --> 00:02:55,580
So these are the positions that we are going to compare zero with position one one with position two

66
00:02:55,580 --> 00:02:57,380
two with position three.

67
00:02:57,620 --> 00:03:04,460
Now after again remember we are not comparing the last element because as we said this is already fixed.

68
00:03:04,460 --> 00:03:09,560
Eight is at the right position, which is the largest value and it is at the right most position.

69
00:03:09,560 --> 00:03:14,540
Now we keep doing this, we keep having passes till in one pass.

70
00:03:14,540 --> 00:03:20,930
If we don't do any swap, if you don't do any swap in a particular pass, that means it's already sorted,

71
00:03:20,930 --> 00:03:21,380
right?

72
00:03:21,380 --> 00:03:24,530
If it's not already sorted, we would have done at least one pass.

73
00:03:24,530 --> 00:03:31,160
But if in one pass we don't do any swaps, it means that the array is sorted and we can stop now.

74
00:03:31,160 --> 00:03:34,610
For example, in this pass we can see that we'll compare two and three.

75
00:03:34,610 --> 00:03:36,380
So they are in order.

76
00:03:36,380 --> 00:03:38,000
So we don't need to swap.

77
00:03:38,000 --> 00:03:39,530
We will compare three and seven.

78
00:03:39,530 --> 00:03:40,340
They are in order.

79
00:03:40,340 --> 00:03:41,480
So we don't need to swap.

80
00:03:41,480 --> 00:03:43,670
But seven and one they are not in order.

81
00:03:43,670 --> 00:03:44,810
So we will swap right.

82
00:03:44,810 --> 00:03:46,790
So we cannot stop at this point also.

83
00:03:46,790 --> 00:03:51,950
So after doing this swap the array will look like this 23178.

84
00:03:51,950 --> 00:03:54,770
We have swapped these two so we got one and seven over here.

85
00:03:55,220 --> 00:03:57,140
Now this is the second pass.

86
00:03:57,140 --> 00:04:04,610
Now notice that at the end of the second pass the second largest value is at its right position after

87
00:04:04,610 --> 00:04:08,240
the end of the first pass, the largest value was that its right position.

88
00:04:08,240 --> 00:04:15,170
Now after the second pass, we have the second largest value at the second place from the right.

89
00:04:15,170 --> 00:04:15,350
Right.

90
00:04:15,350 --> 00:04:16,340
Which is this place.

91
00:04:16,340 --> 00:04:20,690
Now, in the next pass, we don't need to compare these two values.

92
00:04:20,690 --> 00:04:22,400
They are fixed, they are in the right position.

93
00:04:22,400 --> 00:04:26,330
So we just need to do two comparisons two and three and three and one.

94
00:04:26,330 --> 00:04:29,330
Now when we do two and three they are already in order.

95
00:04:29,330 --> 00:04:30,710
So we don't need to swap them.

96
00:04:30,710 --> 00:04:33,680
But when we compare three and one they are not in order.

97
00:04:33,680 --> 00:04:37,580
So we will swap them and we get two, one, three, seven and eight.

98
00:04:37,580 --> 00:04:43,880
Now in the next pass we will compare only two and one because over here notice the third largest element,

99
00:04:43,880 --> 00:04:45,860
which is three is now in the correct place.

100
00:04:45,860 --> 00:04:50,210
So these three elements or integers are in the correct place.

101
00:04:50,210 --> 00:04:52,790
So we don't need to compare them any further.

102
00:04:52,790 --> 00:04:55,580
So in the next pass we will only compare these two.

103
00:04:55,580 --> 00:04:57,410
And they need to be changed.

104
00:04:57,410 --> 00:04:58,580
The order has to be changed.

105
00:04:58,580 --> 00:04:59,720
So we change them.

106
00:04:59,720 --> 00:05:04,430
We swap them and we get 12378 which is the correct order.

107
00:05:04,430 --> 00:05:07,430
So the input array has been sorted.

108
00:05:07,430 --> 00:05:09,500
So this is how Bubblesort works.

109
00:05:09,500 --> 00:05:16,760
Now just to demonstrate in the case where we had the input array as 23718, we saw that we had to make

110
00:05:16,760 --> 00:05:18,050
swaps up to the end.

111
00:05:18,050 --> 00:05:21,710
Right now let's say that the input array is partially sorted.

112
00:05:21,710 --> 00:05:23,840
Like let's say it's 12837.

113
00:05:23,840 --> 00:05:25,310
So it's partially sorted.

114
00:05:25,310 --> 00:05:28,010
Now in the first pass we'll compare one and two.

115
00:05:28,040 --> 00:05:29,120
We don't need to swap.

116
00:05:29,120 --> 00:05:30,440
We'll compare two and eight.

117
00:05:30,470 --> 00:05:31,910
We don't need to swap.

118
00:05:31,910 --> 00:05:34,190
We'll compare then eight and three.

119
00:05:34,190 --> 00:05:35,840
In this case we need to swap right.

120
00:05:35,840 --> 00:05:40,370
So when we swap them the array will become 12387.

121
00:05:40,370 --> 00:05:42,800
And then we will compare eight and seven.

122
00:05:42,800 --> 00:05:43,130
Right.

123
00:05:43,130 --> 00:05:45,680
So when we compare eight and seven again we will swap.

124
00:05:45,680 --> 00:05:48,080
And we get 12378.

125
00:05:48,080 --> 00:05:50,630
And you can see that this is already sorted.

126
00:05:50,630 --> 00:05:50,840
Right.

127
00:05:50,840 --> 00:05:53,150
And this happened in one pass.

128
00:05:53,750 --> 00:06:00,020
Now what happens is in the next pass we will not take, we will not compare this element because as

129
00:06:00,020 --> 00:06:03,980
we've discussed after the first pass, this is already in the right place.

130
00:06:03,980 --> 00:06:06,380
But we will do these comparisons right.

131
00:06:06,380 --> 00:06:12,890
We'll compare the positions zero and one, the values at index zero and one, the values at index one

132
00:06:12,890 --> 00:06:15,290
and two, the value at index two and three.

133
00:06:15,290 --> 00:06:18,020
So we'll make these comparisons in the next pass.

134
00:06:18,020 --> 00:06:20,210
And you can see that over here.

135
00:06:20,210 --> 00:06:22,370
We don't need to make any swaps right over here.

136
00:06:22,370 --> 00:06:24,680
We don't need any any swaps when we compare.

137
00:06:24,800 --> 00:06:25,160
These two.

138
00:06:25,160 --> 00:06:26,390
We don't need any swaps.

139
00:06:26,390 --> 00:06:29,390
And when we compare these two, we don't need any swaps.

140
00:06:29,390 --> 00:06:32,180
So there is no swap in this pass.

141
00:06:32,180 --> 00:06:37,220
And that means that this array is already sorted and therefore we can stop.

142
00:06:37,220 --> 00:06:39,500
So this is how the bubble sort works.

143
00:06:39,500 --> 00:06:45,140
And let's take a quick look at the complexity analysis of the bubble sort.

144
00:06:45,470 --> 00:06:50,960
Now over here you can see that the time complexity of the bubble sort is O of n square.

145
00:06:50,960 --> 00:06:51,320
Right.

146
00:06:51,320 --> 00:06:53,570
Why is that so in one pass.

147
00:06:53,570 --> 00:06:57,980
In one pass we are doing n operations or almost N operations.

148
00:06:57,980 --> 00:06:58,400
Right?

149
00:06:58,400 --> 00:07:01,220
We are comparing two and three, three and seven etc..

150
00:07:01,220 --> 00:07:01,400
Right.

151
00:07:01,400 --> 00:07:04,040
So we are doing almost n operations in one pass.

152
00:07:04,280 --> 00:07:09,650
Now if we have n elements we need to do almost n passes.

153
00:07:09,950 --> 00:07:10,340
Right.

154
00:07:10,340 --> 00:07:15,680
So that's why n into n the time complexity is O of n square.

155
00:07:17,250 --> 00:07:19,110
Now what about.

156
00:07:19,200 --> 00:07:22,950
And again remember this is when we implement this you can just think of it again.

157
00:07:22,950 --> 00:07:25,140
It will become more clear when we look at the code.

158
00:07:25,140 --> 00:07:27,990
This will be implemented as a nested for loop.

159
00:07:27,990 --> 00:07:28,380
Right.

160
00:07:28,380 --> 00:07:30,630
We we could write this as a nested for loop.

161
00:07:30,630 --> 00:07:33,660
And when you have a nested for loop it's o of n square, right.

162
00:07:33,660 --> 00:07:38,670
Because for each element again you're traversing the given array.

163
00:07:38,910 --> 00:07:39,390
Right.

164
00:07:39,390 --> 00:07:42,600
So we'll see that again more clearly when we look at the code.

165
00:07:42,600 --> 00:07:45,180
You can also think of it in this manner.

166
00:07:45,180 --> 00:07:52,470
Over here we have seen that after one pass the largest element is at the right place, right at the

167
00:07:52,470 --> 00:07:54,450
right most place after one pass.

168
00:07:54,570 --> 00:08:01,650
So if we have n elements, the worst case, we would need n passes to get all of them in their respective

169
00:08:01,650 --> 00:08:02,430
right place.

170
00:08:02,430 --> 00:08:07,800
So that's why for n elements we need n passes and in one pass we are doing n operations.

171
00:08:07,800 --> 00:08:12,270
Therefore, the time complexity of this solution is O of n square.

172
00:08:12,300 --> 00:08:14,370
Now what about the space complexity?

173
00:08:14,370 --> 00:08:19,860
The space complexity is O of one because we are not using any additional memory, right?

174
00:08:19,860 --> 00:08:22,050
We are just swapping in place.

175
00:08:22,050 --> 00:08:24,570
We are not making a new array or something like that.

176
00:08:24,570 --> 00:08:27,990
So the space complexity of this solution is O of one.

177
00:08:27,990 --> 00:08:33,420
Now remember O of n square is not the best case scenario of bubble sort.

178
00:08:33,450 --> 00:08:38,610
The best case scenario happens when you are already given when the input array itself is sorted.

179
00:08:38,610 --> 00:08:39,150
For example.

180
00:08:39,150 --> 00:08:47,250
In this case, if the input array itself was 1378, after one pass, we will identify that no swap had

181
00:08:47,250 --> 00:08:49,140
to be made and we can stop right?

182
00:08:49,140 --> 00:08:55,320
In that case, the time complexity would be O of N, but that's not the average or the worst case.

183
00:08:55,320 --> 00:08:56,580
That's the best case, right?

184
00:08:56,580 --> 00:08:58,950
So we cannot say that that's the time complexity.

185
00:08:58,950 --> 00:09:02,250
The time complexity of the bubble sort is O of n square.