1
00:00:00,720 --> 00:00:03,750
So we have successfully coded the bubble sort.

2
00:00:03,780 --> 00:00:05,790
Now let's take a sample input.

3
00:00:05,790 --> 00:00:10,470
Let's say it's one, two four, five, three and walk through the code and see what's happening over

4
00:00:10,470 --> 00:00:10,890
here.

5
00:00:10,920 --> 00:00:13,200
Now we call the bubble sort function.

6
00:00:13,200 --> 00:00:14,520
And we pass this array.

7
00:00:14,550 --> 00:00:17,070
Now initially sorted is set to false.

8
00:00:17,070 --> 00:00:17,580
All right.

9
00:00:17,580 --> 00:00:19,980
And the counter is equal to zero.

10
00:00:20,340 --> 00:00:20,700
All right.

11
00:00:20,730 --> 00:00:22,050
Now sorted is false.

12
00:00:22,050 --> 00:00:26,520
So we come into the while loop and immediately we set sorted to true.

13
00:00:26,550 --> 00:00:29,400
All right now I is equal to zero.

14
00:00:29,430 --> 00:00:29,880
Okay.

15
00:00:29,880 --> 00:00:31,200
So I is equal to zero.

16
00:00:31,200 --> 00:00:38,640
And this will keep repeating till I is no longer less than array dot length minus one minus counter.

17
00:00:38,820 --> 00:00:40,440
So over here the length is five.

18
00:00:40,440 --> 00:00:42,360
So five minus one is four.

19
00:00:42,360 --> 00:00:45,390
So it will keep repeating till three right.

20
00:00:45,390 --> 00:00:46,800
It should be less than four.

21
00:00:46,800 --> 00:00:48,510
So it will repeat for zero.

22
00:00:48,510 --> 00:00:51,210
It will work for one two and three right.

23
00:00:51,210 --> 00:00:52,110
Again remember.

24
00:00:52,110 --> 00:00:52,950
Why is that so.

25
00:00:52,950 --> 00:00:55,920
Because we need to compare a value with the next value.

26
00:00:55,920 --> 00:01:01,290
So if we keep if if we had an equal to over here, we would go till I till the last element.

27
00:01:01,290 --> 00:01:04,740
But then over here you can see that we have array I plus one.

28
00:01:04,740 --> 00:01:07,350
So there would nothing be there as the next element.

29
00:01:07,350 --> 00:01:10,020
That's why we have only less than over here.

30
00:01:10,020 --> 00:01:13,410
So this will keep repeating for I012 and three.

31
00:01:13,860 --> 00:01:14,310
All right.

32
00:01:14,340 --> 00:01:16,140
Now initially I is equal to zero.

33
00:01:16,140 --> 00:01:18,300
Now I plus one is equal to one.

34
00:01:18,300 --> 00:01:20,460
So we are comparing these two elements right.

35
00:01:20,460 --> 00:01:23,310
The elements at the zeroth and the one index.

36
00:01:23,310 --> 00:01:30,090
So let me write the indices in a small manner over here 0123 and four.

37
00:01:30,090 --> 00:01:32,700
We are comparing the indices at zero and one.

38
00:01:32,700 --> 00:01:36,330
And we see that they are not uh.

39
00:01:36,330 --> 00:01:39,000
So over here we see that they are already in order.

40
00:01:39,000 --> 00:01:40,830
So we don't call the swap function.

41
00:01:40,830 --> 00:01:43,050
Now after this I is equal to one, right?

42
00:01:43,050 --> 00:01:43,890
I is equal to one.

43
00:01:43,890 --> 00:01:45,450
And we are comparing these two.

44
00:01:45,450 --> 00:01:47,130
Now these two are also in order.

45
00:01:47,130 --> 00:01:48,990
So we don't call the swap function.

46
00:01:48,990 --> 00:01:50,580
After this I becomes two.

47
00:01:50,580 --> 00:01:53,430
Right when I is equal to two we are comparing two and three.

48
00:01:53,430 --> 00:01:55,860
The values at the indices two and three.

49
00:01:55,860 --> 00:01:57,000
They are also in order.

50
00:01:57,000 --> 00:02:00,240
So we don't call the swap function again we increment I.

51
00:02:00,270 --> 00:02:02,700
So as we have discussed over here it goes till three.

52
00:02:02,700 --> 00:02:05,790
So when I is equal to three we are comparing these two right.

53
00:02:05,790 --> 00:02:07,920
The values at index three and four.

54
00:02:07,920 --> 00:02:09,300
Now these are not in order.

55
00:02:09,300 --> 00:02:12,960
So we call the swap function and we swap five and three right.

56
00:02:12,960 --> 00:02:18,060
So when we swap five and three the array becomes 1243 and five.

57
00:02:18,060 --> 00:02:19,860
So these two values are swapped.

58
00:02:19,860 --> 00:02:24,120
And when we enter over here we set sorted is equal to false.

59
00:02:24,120 --> 00:02:26,730
So when we started we had made sorted true.

60
00:02:26,730 --> 00:02:30,030
But in this pass this is one pass right.

61
00:02:30,030 --> 00:02:32,430
So in this pass we had to make a swap.

62
00:02:32,430 --> 00:02:34,110
Therefore sorted became false.

63
00:02:34,110 --> 00:02:37,650
And we come out of the for loop we increment counter.

64
00:02:37,650 --> 00:02:38,970
So counter was zero over here.

65
00:02:38,970 --> 00:02:40,980
So counter becomes one right.

66
00:02:40,980 --> 00:02:43,590
And we check whether sorted is false.

67
00:02:43,590 --> 00:02:45,960
So sorted is false because it became false over here.

68
00:02:45,960 --> 00:02:49,620
So again we enter the while loop and sorted is set to true.

69
00:02:49,620 --> 00:02:50,040
Right.

70
00:02:50,040 --> 00:02:55,470
And then for I from zero up to array dot length minus one minus counter.

71
00:02:55,470 --> 00:02:56,940
So in this case counter is one.

72
00:02:56,940 --> 00:03:01,560
So array dot length is five five minus one is four minus one is three.

73
00:03:01,560 --> 00:03:03,900
So it has to be less than three right.

74
00:03:03,900 --> 00:03:06,450
So it will work for zero one and two.

75
00:03:06,450 --> 00:03:09,420
So these are the three iterations that will happen over here right.

76
00:03:09,420 --> 00:03:11,850
Remember we don't need to compare the last element.

77
00:03:11,850 --> 00:03:13,800
It's already in the correct position.

78
00:03:13,800 --> 00:03:14,970
We have discussed that right.

79
00:03:14,970 --> 00:03:20,760
So that's why we just need these three uh comparisons in this particular pass.

80
00:03:20,760 --> 00:03:24,150
So when I is equal to zero we are going to compare these two values.

81
00:03:24,150 --> 00:03:26,160
And they are already in order.

82
00:03:26,160 --> 00:03:28,920
When I is equal to one we are going to compare these two values.

83
00:03:28,920 --> 00:03:30,060
They're also in order.

84
00:03:30,060 --> 00:03:33,720
And when I is equal to two we are going to compare these two.

85
00:03:33,720 --> 00:03:35,460
And these two are not in order right.

86
00:03:35,460 --> 00:03:37,320
So again we will enter over here.

87
00:03:37,320 --> 00:03:38,910
We will call the swap function.

88
00:03:38,910 --> 00:03:41,460
And we will swap these two values right.

89
00:03:41,460 --> 00:03:43,680
So we get 12345.

90
00:03:44,160 --> 00:03:45,600
And sorted is set to false.

91
00:03:45,600 --> 00:03:46,110
Right.

92
00:03:46,110 --> 00:03:52,440
And we come out of this right now when we are coming out of this and it was at I is equal to two.

93
00:03:52,440 --> 00:03:52,650
Right.

94
00:03:52,650 --> 00:03:53,460
So this is over.

95
00:03:53,460 --> 00:03:56,280
That's why we come out and we increment the counter.

96
00:03:56,280 --> 00:03:57,960
Now counter is set to two.

97
00:03:57,990 --> 00:03:59,400
Right counter becomes two.

98
00:03:59,430 --> 00:04:00,600
Let me write that over here.

99
00:04:00,600 --> 00:04:01,950
Counter becomes two.

100
00:04:01,950 --> 00:04:04,920
And again sorted is false right.

101
00:04:04,920 --> 00:04:06,000
We made it false over here.

102
00:04:06,000 --> 00:04:07,500
So it enters the while loop.

103
00:04:07,500 --> 00:04:08,970
And we check over here.

104
00:04:08,970 --> 00:04:14,040
While I is less than array dot length which is five five minus one is four minus two which is two.

105
00:04:14,070 --> 00:04:15,540
So it has to be less than two.

106
00:04:15,570 --> 00:04:17,580
So it will work only for zero and one.

107
00:04:17,580 --> 00:04:18,780
But that's fine.

108
00:04:18,780 --> 00:04:22,260
So this at point zero will compare these two right.

109
00:04:23,150 --> 00:04:25,640
And at point one we'll compare these two.

110
00:04:25,640 --> 00:04:26,030
Right.

111
00:04:26,030 --> 00:04:27,320
So they are already in order.

112
00:04:27,320 --> 00:04:29,390
And these two are already in their fixed position.

113
00:04:29,390 --> 00:04:30,800
So we don't need to compare them.

114
00:04:30,800 --> 00:04:35,240
So at this point you can see that we did not make any swap.

115
00:04:35,240 --> 00:04:37,550
Therefore sorted stays true.

116
00:04:37,550 --> 00:04:40,970
We made sorted true over here and sorted stays true.

117
00:04:41,000 --> 00:04:44,690
You can see that all these five elements are sorted right.

118
00:04:44,690 --> 00:04:47,240
So that's why we can stop at this point.

119
00:04:47,240 --> 00:04:48,560
Sorted is set to true.

120
00:04:48,560 --> 00:04:53,930
And we can return the array and we have the array in sorted manner.

121
00:04:53,930 --> 00:04:58,670
Now this is how we solved, uh this is how the bubble sort works.

122
00:04:58,670 --> 00:05:01,190
Now what's the time complexity of this.

123
00:05:01,190 --> 00:05:04,730
We have seen that the time complexity of this is o of n square.

124
00:05:04,730 --> 00:05:09,230
Why is that so over here you can see that we are making n passes.

125
00:05:09,230 --> 00:05:09,650
Right.

126
00:05:09,650 --> 00:05:13,070
So, uh, how how do we how do we say that.

127
00:05:14,180 --> 00:05:16,520
And passes is the worst case scenario.

128
00:05:16,520 --> 00:05:19,550
If all the elements had to be shifted right?

129
00:05:19,550 --> 00:05:21,230
If swaps kept on happening.

130
00:05:21,230 --> 00:05:25,220
Now, when we look at the time complexity, we always look at the worst case scenario.

131
00:05:25,220 --> 00:05:29,300
Right now the process is taken care by the while loop, right?

132
00:05:29,300 --> 00:05:32,810
So we keep doing the while loop till we need to make more passes.

133
00:05:32,810 --> 00:05:37,940
And in each pass you can see that over here in the for loop we are doing N operations.

134
00:05:37,940 --> 00:05:42,140
So over here we have the while loop which which is contributing N operations.

135
00:05:42,140 --> 00:05:45,770
And in each of these N operations we are having the for loop.

136
00:05:45,770 --> 00:05:46,010
Right.

137
00:05:46,010 --> 00:05:48,500
So this is nested inside the while loop.

138
00:05:48,500 --> 00:05:51,080
And for each one of these we are doing n operations.

139
00:05:51,080 --> 00:05:55,280
So that's why the time complexity is n into n which is n square.

140
00:05:55,280 --> 00:05:58,970
So the time complexity is O of n square right now.

141
00:05:59,480 --> 00:06:00,410
So n passes.

142
00:06:00,410 --> 00:06:02,990
And in each pass we're doing n operations.

143
00:06:02,990 --> 00:06:05,030
In one pass we have n operations.

144
00:06:05,030 --> 00:06:08,450
So that's why n into n n square is the time complexity.

145
00:06:08,450 --> 00:06:11,180
And the space complexity is O of one.

146
00:06:11,180 --> 00:06:11,900
Why is that so.

147
00:06:11,900 --> 00:06:14,210
Because we are not using any additional space.

148
00:06:14,210 --> 00:06:15,830
We are not making a new array.

149
00:06:15,830 --> 00:06:19,820
So it's running in constant space or O of one.