1
00:00:00,750 --> 00:00:05,580
Hi everyone, I hope you have given it a try to code out the bubble sort, which we discussed in the

2
00:00:05,580 --> 00:00:06,570
previous video.

3
00:00:06,570 --> 00:00:09,000
Now in this video, let's do it together.

4
00:00:09,000 --> 00:00:13,620
And for this we will create a function and let's call it bubble sort.

5
00:00:14,830 --> 00:00:17,920
And this function is going to take in an array as input.

6
00:00:17,950 --> 00:00:22,570
Now, as we've seen in the previous video, what we are going to do is we are going to make several

7
00:00:22,570 --> 00:00:26,200
passes through the array till the given array is sorted.

8
00:00:26,230 --> 00:00:30,580
Now we need to have a variable to know whether the array is sorted or not.

9
00:00:30,580 --> 00:00:30,880
Right.

10
00:00:30,880 --> 00:00:32,920
So let's call that sorted.

11
00:00:32,920 --> 00:00:36,130
And initially let's make it false.

12
00:00:36,130 --> 00:00:39,160
Now when we do a particular pass through the array.

13
00:00:39,160 --> 00:00:46,600
And if we notice that we don't need to do any swaps of a particular value in the array and the next

14
00:00:46,600 --> 00:00:49,450
value, it means that the array is already sorted, right?

15
00:00:49,450 --> 00:00:54,250
For example, if the given array is this 112345, right?

16
00:00:54,250 --> 00:01:00,370
So when we do one pass, we will see that we do not need to make any swaps because this array is already

17
00:01:00,370 --> 00:01:00,880
sorted.

18
00:01:00,880 --> 00:01:06,940
So at this point we can know that this array is sorted and we can stop and exit and return the function.

19
00:01:06,940 --> 00:01:10,060
So we'll use this variable over here to track that.

20
00:01:10,060 --> 00:01:12,130
And we will need one more variable.

21
00:01:12,130 --> 00:01:13,450
Let's call it counter.

22
00:01:13,450 --> 00:01:15,790
And initially that's equal to zero.

23
00:01:16,240 --> 00:01:21,580
Now as we've seen in the previous video, in one pass we will get the largest value to the rightmost

24
00:01:21,580 --> 00:01:22,360
place right.

25
00:01:22,360 --> 00:01:29,680
So for example let's say the input array was 54321.

26
00:01:29,680 --> 00:01:36,460
Now after one pass after one pass is over, the array would look like this, right?

27
00:01:36,610 --> 00:01:42,310
Whatever elements are there in different places, the rightmost element that's one, two three, four,

28
00:01:42,310 --> 00:01:42,520
five.

29
00:01:42,520 --> 00:01:44,800
The fifth element would be the largest element.

30
00:01:44,800 --> 00:01:46,570
That is, five will come over here, right.

31
00:01:46,570 --> 00:01:53,680
So we in the next pass, we don't need to take into take into consideration whatever we got over here.

32
00:01:53,680 --> 00:01:58,750
So that's why we need to know how many integers are already sorted in the right most places.

33
00:01:58,750 --> 00:02:01,210
And for this we have this counter over here.

34
00:02:01,210 --> 00:02:07,960
Now initially we set it to zero and we will have a while loop and let this while loop keep operating

35
00:02:07,990 --> 00:02:09,670
till sorted is true.

36
00:02:09,670 --> 00:02:11,500
So initially sorted is false.

37
00:02:11,500 --> 00:02:14,740
So it will go into the while loop right?

38
00:02:14,740 --> 00:02:15,820
So initially it's false.

39
00:02:15,820 --> 00:02:16,720
It will go in.

40
00:02:16,720 --> 00:02:21,370
Now when once we are inside this while loop let's set sorted to true.

41
00:02:22,150 --> 00:02:22,660
All right.

42
00:02:22,660 --> 00:02:28,450
Now, if we need to make any swaps in the further conditions that we're going to write, we will set

43
00:02:28,450 --> 00:02:31,840
sorted again to false so that the loop has to run again.

44
00:02:32,050 --> 00:02:35,890
Now to loop through the elements let's use a for loop.

45
00:02:35,890 --> 00:02:41,920
So for let I equal to zero I less than array dot length.

46
00:02:43,080 --> 00:02:45,750
Minus one minus counter.

47
00:02:47,780 --> 00:02:48,980
I plus plus.

48
00:02:49,520 --> 00:02:52,940
And over here inside this for loop we will do the comparison.

49
00:02:52,940 --> 00:02:58,700
Now notice over here that we have our I less than RA dot length minus one minus counter.

50
00:02:58,700 --> 00:03:01,220
So initially the counter is zero.

51
00:03:01,220 --> 00:03:05,690
So we will uh let the value of I go from zero.

52
00:03:05,690 --> 00:03:07,910
Let's say this is the given array.

53
00:03:07,910 --> 00:03:10,220
So the length of this array is five.

54
00:03:10,220 --> 00:03:11,840
So length is equal to five.

55
00:03:11,840 --> 00:03:18,320
So we will have I values from 0 to 4 right 123 and four.

56
00:03:18,320 --> 00:03:22,640
Now when I is equal to uh sorry up to three right.

57
00:03:22,640 --> 00:03:27,710
It's going to go up to three because array dot length is five minus one is four.

58
00:03:27,710 --> 00:03:29,390
But we don't have less than equal to.

59
00:03:29,390 --> 00:03:31,910
We just have less than r dot length minus one.

60
00:03:31,910 --> 00:03:33,890
And counter at this point is equal to zero.

61
00:03:33,890 --> 00:03:35,000
Now why we do that.

62
00:03:35,000 --> 00:03:37,040
Because we always need a next element right.

63
00:03:37,040 --> 00:03:41,720
We are going to compare array at the ith index and array at the I plus one th index.

64
00:03:41,720 --> 00:03:44,330
So that's why we need over here only less than.

65
00:03:44,330 --> 00:03:46,670
So I less than array dot length minus one.

66
00:03:46,670 --> 00:03:48,170
And then minus counter.

67
00:03:48,170 --> 00:03:55,160
Because we have seen that in every pass we will fix the position the the element at the rightmost part

68
00:03:55,160 --> 00:03:56,990
of the array, the greatest one.

69
00:03:56,990 --> 00:03:59,540
In the first pass we will get the greatest value over here.

70
00:03:59,540 --> 00:04:04,670
In the second pass, we will get the second greatest in the second position from the right, and so

71
00:04:04,670 --> 00:04:05,270
on and so forth.

72
00:04:05,270 --> 00:04:05,540
Right.

73
00:04:05,540 --> 00:04:07,490
So that's why we have the counter over here.

74
00:04:08,030 --> 00:04:08,510
All right.

75
00:04:08,510 --> 00:04:10,490
Now we are inside the for loop.

76
00:04:10,490 --> 00:04:18,110
Now let's compare the elements in the given array at the ith index and the I plus one th index.

77
00:04:18,110 --> 00:04:22,850
So if array at I is greater than array at I plus one.

78
00:04:23,390 --> 00:04:25,370
So that means we need to swap them right.

79
00:04:25,370 --> 00:04:28,430
So we need to sort in ascending order.

80
00:04:28,430 --> 00:04:31,520
So array of I should be less than array of I plus one.

81
00:04:31,520 --> 00:04:34,100
So if the order is wrong then we need to swap it.

82
00:04:34,100 --> 00:04:37,940
So for this let's call a swap function which we need to write.

83
00:04:37,940 --> 00:04:38,960
Write it right.

84
00:04:38,960 --> 00:04:43,760
And into this function we will pass the array and we will pass the value of I.

85
00:04:43,760 --> 00:04:50,600
And from I we can always calculate I plus one and once swap is done and again remember we will be writing

86
00:04:50,600 --> 00:04:51,530
swap over here.

87
00:04:51,530 --> 00:04:55,580
So let me just write a placeholder over here swap function swap.

88
00:04:55,580 --> 00:04:58,610
And it takes in the array and it takes in the value I.

89
00:04:58,610 --> 00:05:01,250
And we have the remaining function over here.

90
00:05:01,980 --> 00:05:08,700
Now, if we have to do a swap in a particular pass, then it means that the array is not sorted, so

91
00:05:08,700 --> 00:05:10,410
we cannot be sure that it's sorted.

92
00:05:10,410 --> 00:05:12,960
So we set sorted to false.

93
00:05:13,880 --> 00:05:19,850
Only when we have one complete pass without any swap, we can be sure that the array is sorted.

94
00:05:19,880 --> 00:05:27,350
So at this point we set it to false, and once we are out of this for loop right, we need to increment

95
00:05:27,350 --> 00:05:28,220
the counter.

96
00:05:28,730 --> 00:05:29,990
Counter plus plus.

97
00:05:30,230 --> 00:05:36,320
And once we are out of this for loop and out of this while loop, this will come out of this while loop

98
00:05:36,320 --> 00:05:37,610
when sorted is true, right?

99
00:05:37,610 --> 00:05:42,530
So that means the array is sorted and we just need to return the array at this point.

100
00:05:42,530 --> 00:05:45,260
And we have our solution except the swap function.

101
00:05:45,260 --> 00:05:50,930
So the swap function is a simple function where we will swap the values in the given array in place.

102
00:05:50,930 --> 00:05:51,380
Right.

103
00:05:51,380 --> 00:05:53,990
We're not using any extra space in place.

104
00:05:53,990 --> 00:05:58,730
We're going to swap the positions at the Ith and I plus one index.

105
00:05:58,730 --> 00:06:01,610
And yes we will use a temp temporary variable for that.

106
00:06:01,610 --> 00:06:06,650
So let temp equal to array at the ith position.

107
00:06:06,650 --> 00:06:08,480
And then let's.

108
00:06:09,540 --> 00:06:10,470
Say that, right?

109
00:06:10,500 --> 00:06:16,380
I is equal to r at I plus one and array at I plus one.

110
00:06:17,390 --> 00:06:18,980
Is equal to temp.

111
00:06:19,070 --> 00:06:23,480
So yes, we have swapped the values and here we have our solution.

112
00:06:23,480 --> 00:06:25,160
Now let's test it out.

113
00:06:25,340 --> 00:06:30,590
Let's console dot log and call our function Bubblesort.

114
00:06:30,590 --> 00:06:32,810
And let's pass in an array.

115
00:06:32,810 --> 00:06:34,730
Let's define the array over here.

116
00:06:34,730 --> 00:06:43,400
Let's take array A as let's say uh 14352.

117
00:06:43,430 --> 00:06:43,910
All right.

118
00:06:43,910 --> 00:06:47,450
Now let's run this and see what we are going to get.

119
00:06:48,690 --> 00:06:50,670
So I'm going to run this now.

120
00:06:52,650 --> 00:06:53,070
All right.

121
00:06:53,070 --> 00:06:59,250
So I've run the algorithm that we have written and we are getting 12345 which is correct.

122
00:06:59,250 --> 00:07:01,050
So our algorithm is working.

123
00:07:01,050 --> 00:07:02,850
Let's try a few more cases.

124
00:07:02,850 --> 00:07:06,120
Let's say we have uh another array over here.

125
00:07:06,300 --> 00:07:15,720
Let's write it as 947 minus one, minus three and five and five.

126
00:07:16,080 --> 00:07:16,590
Right.

127
00:07:16,590 --> 00:07:19,710
So we pass this and let's call our function.

128
00:07:19,710 --> 00:07:24,000
And we get minus three minus one 45579 which is sorted.

129
00:07:24,000 --> 00:07:26,610
So yes our algorithm is working.