Bubble Sorting

Bubble Sorting is one of the most commonly used sorting techniques among beginners. Although not the best sorting algorithm but bubble sort offers you a clean and concise algorithm and could be used if the input size is not very large.
In a general bubble sort technique:

Worst Case Complexity:        O(n^2)
Average Case Complexity:    O(n^2)
Best Case Complexity:          O(n)

The best complexity for a sorting technique so far is O(n logn).

Concept of Bubble Sorting:

In bubble sorting we basically iterate through an array and if we find that two constants are not in correct order then swap their position. Repeat this process until the array is sorted.

For example:

Consider an integer array ar={4,6,2,3,1,5}

We need to sort array in increasing or ascending order.

Lets mark the index position as i. Initially i=0.

Now we will check that if ar[i] and ar[i+1] are not in correct order, if so then we will swap them otherwise we will increment i by 1 till it reaches array's limit-1.

Since 4 is less than 6 therefore they are in correct order therefore we will increment the value of i by 1.

Now 6 is not less than 2 therefore we will swap them.

We will continue this process.

So after first cycle Array will look like:

ar={4,2,3,1,5,6}

Now what we have to do is to repeat this cycle again and again till the array is sorted.

A naive programmer's approach to this algorithm is:

Here we are iterating an outer loop in x for the number of elements in the array and inner loop in y for comparison.

We are comparing each and every consecutive elements and replacing them wherever necessary.

But in this code, no matter what case it is, the complexity remains O(n^2).

We have to improve the code.

Working of a Binary Code:

Lets take an array for example:

 ar={5,4,3,2,1}

After 1st cycle the array will look like:

{4,3,2,1,5}

2nd Cycle:

{3,2,1,4,5}

3rd Cycle:

{2,3,1,4,5}

4th Cycle:

{1,2,3,4,5}

5th Cycle:

{1,2,3,4,5}

The point to be noted is that at the end of every cycle at least one element is placed at its correct position. Therefore at the end of 'i' cycles 'i' elements will be in their correct position but some programmers generally overlook is the fact that when n-1 elements are in right position then the nth element will also be in its right position (n being the number of elements in the array).

So what we can do is:

       for(int x=0;x<n-1;x++)

        {

            for(int y=0;y<n-1;y++)

            {

                if(ar[y]>ar[y+1])

                {

                    int temp=ar[y];

                    ar[y]=ar[y+1];

                    ar[y+1]=temp;

                }

            }

        }

That is we do one iteration less than before.

But wait, there is still some redundancy.

To check that out lets take our original array as example:

ar={4,6,2,3,1,5}

1st Cycle:

ar={4,2,3,1,5,6}

2nd Cycle:

ar={2,3,1,4,5,6,}

3rd Cycle:

ar={2,1,3,4,5,6}

4th Cycle:

ar={1,2,3,4,5,6}

5th Cycle:

ar={1,2,3,4,5,6}

Here, even after decreasing the outer iteration by one, we are still having redundant steps.

The problem is that if the array is not sorted then swapping is done at least one. But if there is no swapping then we can say that the array is sorted so what we can do is to iterate the outer loop till the array is not sorted or till there is at least a single swapping done in the array.

The following is the code for optimization of Bubble Sorting:

Here we have taken the help of a boolean variable, namely sorted, initially sorted is declared as true but if there is at least one swapping done then sorted will be declared as false. If sorted is false or ,we can say, sorted is not true we will iterate again.

So therefore the array is already sorted(best case) the complexity will become O(n) which was not possible in earlier approach.

Although there are many better approach for sorting such as insertion sort, merge sort and quick sort but in the cases where the input is small time doesn't really matters and therefore many programmers use the approach of bubble sorting.