Bubble Sort Programming Code Explained
-------------------------------
21 April 5:53pm
– 28 April 12:34pm 2020
--------------------------------------
Bubble sort
is a programming algorithm to arrange something in a particular order. In this
algorithm, each pair of adjacent elements is compared, and then swapped if they
are in wrong order. To arrange elements in ascending order Bubble Sort starts
by comparing very first two elements to check which one is greater. The smaller
one is set to the left and the bigger one to the right if required. And then it’ll
move on to compare and swap (if needed) the second and the third element, and
so on. At the end of the first iteration of outer loop (in this case i-loop)
we’ll have the greatest number at the last position (right side) of the
elements. Then the second iteration (of the outer loop) will start and check up
to the element which exists just before the last sorted elements. And, of
course, at the end of this second iteration we’ll find the second greatest
element there. The process goes on and on till sorting.
Bubble Sort
Demo Here
Having said
that I’m going to assume you have a clear idea about Bubble Sort demonstration.
If not, please go over the articles I have put at the very bottom of this
tutorial.
More
importantly the main purpose of this tutorial is to explain the Bubble Sort
programming code in an understandable way.
Some fresher
learners happen to understand the Bubble Sort concept. But the problem they
face is they can’t relate the Bubble Sort programming code to its concept. Some
of them want to understand how to figure out the value of the loop condition,
why we take i=n, j=n-1 or j=n-i-1 etc. unless they’re prone to memorize.
Well, so,
without further talking let’s get to the main point.
First up
we’ll see the bubble sort programming code.
for( i = 0; i < n; i++ ){
for( j = 0; j < n-i-1; j++ ){
//
n-i-1 is for ignoring comparisons of elements which have already been compared in earlier
iterations
if( A[j] > A[j+1]){
temp = A[j];
A[j] = A[j+1];
A[J+1] = temp;
}
}
}
Try to understand the code. And then see the image below.
You need to see the code and the image carefully again and again and try
hard to understand. And then go ahead.
We’re going to sort an array with 4 elements, as you see in the image, in
ascending order.
So, now, it’s really important to understand why i-loop condition is i = 3(i.e.
i<n), why not 4, 2, 1 or any other values, and why j = 2, why not other
values.
Well, first you need to understand that i = 3 means 4-time iteration (0 1
2 3).
And j = 2 means 3-time iterations (0 1 2).
Look, we have 4 elements i.e. n = 4. So we need to iterate the i-loop(the
outer loop) 4 times max.
So we can write-
i = 3
=> i < 4
=> i < n [ n represents the number of elements]
I hope it’s clear to you for i values.
Now as for j values….
This j-loop will do the main task like comparing and swapping. Look at the
image below.
As we can see in the picture, j-loop will have to iterate 3 times max.
That is-
j = 2
ð j < 3
ð j < 4-1
ð j < n-1 [ n
represents the number of elements]
Now the question is why we use j < n-i-1 instead of j < n-1 .
At the time of the i-loop’s first iteration (when i=0) the j-loop will
iterate 3 times (0 1 2) up to its maximum limit. And at the end of the i-loop
iteration we have the highest value (here 8) at the last position of the elements
i.e., (3, 2, 5, 8). See the following first iteration demo.
And then at the second iteration of i-loop (when i=1) we need not check
(compare and swap) the last digit as this is the largest value among the
elements. So now j-loop needs to iterate 2 times (0 1) and it will check up to index
2.
As we see, increasing i-values causes the decreasing of j-values. Like-
When i = 0
j < n-i-1
j < 4-0-1
j < 3
Meaning that the j-loop (inner loop) will iterate its maximum limit, i.e, 3
times (0 1 2). See the demo below.
--
When i = 1,
j < 4-1-1
j < 2
Meaning that the j-loop (inner loop) will iterate 2 times(0 1).
--
When i = 2,
j < 4-2-1
j < 1
Meaning that the j-loop (inner loop) will iterate 1 time(0).
--
When i = 3,
j < 4-3-1
j < 0
j = -1
The j-loop condition will be false and it’ll get out of the loop.
And then i will be 4 and that will make this outer loop condition false.
And it will also stop its iteration.
And finally our program will through its result.
If you don’t understand the description above, then don’t be so sorry.
Just follow the following demonstration. I strongly hope that would be helpful.
i =0
j =0
A[j] > A[j+1]
A[0] > A[1]
3 < 5
The
condition is not true. So the two checked elements need not interchange their
positions.
The element
positions will remain the same as before: 3 5 2 8
j =1
A[j]
> A[j+1]
A[1] > A[2]
5 > 2
2 5
The
condition is true. So 5 and 2 will interchange their positions.
Now the
element positions will be: 3 2 5 8 [previous positions 3 5 2 8]
j =2
A[j]
> A[j+1]
A[2] > A[3]
5 < 8
The
condition is not true. So 5 and 8 need not interchange their positions.
The element
positions will remain the same as before: 3 2 5 8 [previous positions 3 2
5 8]
End of the
first iteration of the outer loop (i-loop).
----------------------------------------------------------------
i =1
j =0
A[j]
> A[j+1]
A[0] > A[1]
3 > 2
The
condition is true. So 3 and 2 will interchange their positions.
Now the
element positions will be: 2 3 5 8 [previous positions 3 2 5 8]
j =1
A[j]
> A[j+1]
A[1] > A[2]
3 < 5
The
condition is not true. So 3 and 5 need not interchange their positions.
The element
positions will remain the same: 2 3 5 8 [previous positions 2 3 5
8]
End of the
second iteration of the outer loop (i-loop).
----------------------------------------------------------
i =2
j =0
A[j]
> A[j+1]
A[0] > A[1]
2 < 3
The
condition is not true. So 2 and 3 need not interchange their positions.
Now the
element positions will remain the same: 2 3 5 8 [previous positions 2 3
5 8]
End of the
third iteration of the outer loop (i-loop).
--------------------------------------------------------------------
i =3
For, i = 3;
j = -1. So the inner loop (j-loop) will stop its iteration.
And
simultaneously the outer loop (i-loop) will be out of its iteration for
exceeding its value limit (i=4).
End of the
fourth and last iteration of the outer loop (i-loop).
------------------------------------------------------------------
And
surprisingly enough, our array elements have already been sorted: 2 3 5 8
------------------------------
Resources:
Bubble Sort
Concept Explained
https://www.hackerearth.com/practice/algorithms/sorting/bubble-sort/tutorial/
========================================================
Comments
Post a Comment