Hi everyone, I hope you have given it a try to code out the bubble sort, which we discussed in the
previous video.
Now in this video, let's do it together.
And for this we will create a function and let's call it bubble sort.
And this function is going to take in an array as input.
Now, as we've seen in the previous video, what we are going to do is we are going to make several
passes through the array till the given array is sorted.
Now we need to have a variable to know whether the array is sorted or not.
Right.
So let's call that sorted.
And initially let's make it false.
Now when we do a particular pass through the array.
And if we notice that we don't need to do any swaps of a particular value in the array and the next
value, it means that the array is already sorted, right?
For example, if the given array is this 112345, right?
So when we do one pass, we will see that we do not need to make any swaps because this array is already
sorted.
So at this point we can know that this array is sorted and we can stop and exit and return the function.
So we'll use this variable over here to track that.
And we will need one more variable.
Let's call it counter.
And initially that's equal to zero.
Now as we've seen in the previous video, in one pass we will get the largest value to the rightmost
place right.
So for example let's say the input array was 54321.
Now after one pass after one pass is over, the array would look like this, right?
Whatever elements are there in different places, the rightmost element that's one, two three, four,
five.
The fifth element would be the largest element.
That is, five will come over here, right.
So we in the next pass, we don't need to take into take into consideration whatever we got over here.
So that's why we need to know how many integers are already sorted in the right most places.
And for this we have this counter over here.
Now initially we set it to zero and we will have a while loop and let this while loop keep operating
till sorted is true.
So initially sorted is false.
So it will go into the while loop right?
So initially it's false.
It will go in.
Now when once we are inside this while loop let's set sorted to true.
All right.
Now, if we need to make any swaps in the further conditions that we're going to write, we will set
sorted again to false so that the loop has to run again.
Now to loop through the elements let's use a for loop.
So for let I equal to zero I less than array dot length.
Minus one minus counter.
I plus plus.
And over here inside this for loop we will do the comparison.
Now notice over here that we have our I less than RA dot length minus one minus counter.
So initially the counter is zero.
So we will uh let the value of I go from zero.
Let's say this is the given array.
So the length of this array is five.
So length is equal to five.
So we will have I values from 0 to 4 right 123 and four.
Now when I is equal to uh sorry up to three right.
It's going to go up to three because array dot length is five minus one is four.
But we don't have less than equal to.
We just have less than r dot length minus one.
And counter at this point is equal to zero.
Now why we do that.
Because we always need a next element right.
We are going to compare array at the ith index and array at the I plus one th index.
So that's why we need over here only less than.
So I less than array dot length minus one.
And then minus counter.
Because we have seen that in every pass we will fix the position the the element at the rightmost part
of the array, the greatest one.
In the first pass we will get the greatest value over here.
In the second pass, we will get the second greatest in the second position from the right, and so
on and so forth.
Right.
So that's why we have the counter over here.
All right.
Now we are inside the for loop.
Now let's compare the elements in the given array at the ith index and the I plus one th index.
So if array at I is greater than array at I plus one.
So that means we need to swap them right.
So we need to sort in ascending order.
So array of I should be less than array of I plus one.
So if the order is wrong then we need to swap it.
So for this let's call a swap function which we need to write.
Write it right.
And into this function we will pass the array and we will pass the value of I.
And from I we can always calculate I plus one and once swap is done and again remember we will be writing
swap over here.
So let me just write a placeholder over here swap function swap.
And it takes in the array and it takes in the value I.
And we have the remaining function over here.
Now, if we have to do a swap in a particular pass, then it means that the array is not sorted, so
we cannot be sure that it's sorted.
So we set sorted to false.
Only when we have one complete pass without any swap, we can be sure that the array is sorted.
So at this point we set it to false, and once we are out of this for loop right, we need to increment
the counter.
Counter plus plus.
And once we are out of this for loop and out of this while loop, this will come out of this while loop
when sorted is true, right?
So that means the array is sorted and we just need to return the array at this point.
And we have our solution except the swap function.
So the swap function is a simple function where we will swap the values in the given array in place.
Right.
We're not using any extra space in place.
We're going to swap the positions at the Ith and I plus one index.
And yes we will use a temp temporary variable for that.
So let temp equal to array at the ith position.
And then let's.
Say that, right?
I is equal to r at I plus one and array at I plus one.
Is equal to temp.
So yes, we have swapped the values and here we have our solution.
Now let's test it out.
Let's console dot log and call our function Bubblesort.
And let's pass in an array.
Let's define the array over here.
Let's take array A as let's say uh 14352.
All right.
Now let's run this and see what we are going to get.
So I'm going to run this now.
All right.
So I've run the algorithm that we have written and we are getting 12345 which is correct.
So our algorithm is working.
Let's try a few more cases.
Let's say we have uh another array over here.
Let's write it as 947 minus one, minus three and five and five.
Right.
So we pass this and let's call our function.
And we get minus three minus one 45579 which is sorted.
So yes our algorithm is working.