Bubble Sort - Algorithm (Simple sort techniques)

Hi, I'm going to describe you some simple sorting techniques. This post describes one of the simplest sorting algorithms. Bubble sort. It is done by  comparing and swapping the contiguous elements.
Look at the following unsorted array.

figure 01:Before sorting

1st Round (Consider all five elements)

Step 01:

     First we compare 0th and 1st elements of the array. You can see 0th element is 4.3 and it is larger than 1st element which is 2.5. So we swap 0th and 1st elements.

figure 02:After swapping 0th and 1st elements

Step 02:

In step01 we have done with first two elements. The next step is compare and swap(if necessary) 1st and 2nd elements. Now the 1st element is 4.3 and 2nd element is 3.5. The 1st element is larger than 2nd element.

So we swap 1st and 2nd elements.

figure 03:After swapping 1st and 2nd elements

Step 03:

Compare 2nd and 3rd elements. 2nd element is smaller than 3rd element. So it is not need to swap. 

figure 04:2nd and 3rd elements are not swapped 

Step 04:

Compare 3rd and 4th elements. 3rd is larger than 4th. So we swap.

figure 05:After swapping 3rd and 4th elements

After four steps the 4th element is sorted at the end of the 1st Round. So no need to consider 4th element anymore(4th element already sorted). Therefore we consider only the 0th, 1st, 2nd and 3rd elements in next round. 

2nd Round (consider first four elements)

Step 01:

Compare 0th and 1st elements. 0th is smaller than 1st. So no need to swap.

figure 06

Step 02:

Compare 1st and 2nd elements. 1st is smaller than 2nd. So no need to swap.

figure 07

Step 03:

Compare 2nd and 3rd elements. 2nd is larger than 3rd. So we swap 2nd and 3rd elements.

figure 08:After swapping 2nd and 3rd elements

Now the last two elements are sorted at the end of the 2nd Round. So we not consider 3rd and 4th elements In the next round (3rd and 4th elements already sorted).

3rd Round (Consider first three elements)

Step 01:

Compare 0th and 1st elements. 0th is smaller than 1st. So no need to swap.

figure 09

Step 02:

Compare 1st and 2nd elements. 1st is larger than 2nd. So we swap 1st and 2nd elements.

figure 10: After swapping 1st and 2nd elements

Now all the elements are sorted. :) 

The java code for Bubble Sort is follow 

In BubbleSort class, the most important method is bubbleSort() method. 

The outer for loop :

for(int out=nElemns-1;out>0;out--)  represents the Rounds I described in the algorithm. Executing this loop one time means executing one Round in the Algorithm.In each round it reduces the elements to consider by one. 

According to the five element array I described above, for the first time out is 4(that means we consider all five elements from 0 to 4). 

When the loop executing the second time out is 3(consider first four elements from 0 to 3).

The inner loop: for(in=0;in<out;in++)  represents the number of steps execute in each round. 

As our previous example, In the first Round, the out is 4. which means the number of steps in first Round is 4. Because we compare(always) and swap(when necessary)  4 contiguous pairs of elements in first round. 

When inner loop complete four steps, the outer loop reduce out by one (Because after first round, the last element is sorted and will not consider it again) Which means the number of steps of 2nd Round is 3. Because we compare and swap 3 contiguous pairs of elements in second round.(Because after the first round the 4th element is sorted and not consider in 2nd Round).

The runner class 

Download Code