Bubble Sort

Bubble sort is a simple sorting algorithm. It works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. The algorithm gets its name from the way smaller elements “bubble” to the top of the list. Because it only uses comparisons to operate on elements, it is a comparison sort.

Reference: http://en.wikipedia.org/wiki/Bubble_sort

Rules:

  • In This Algorithm It compares two elements starting from first
  • And it swaps when the first element is greater than second element.

Let’s do bubble sort for five numbers

5 3 4 12 1

First Pass

5 3 4 12 1

5>3, so they are swapping positions

3 5 4 12 1

5>4, so they are swapping positions

3 4 5 12 1

5<12, no swap

3 4 5 12 1

12>1, so they are swapping positions

3 4 5 1 12

Second Pass

3 4 5 1 12

3<4, no swap

3 4 5 1 12

4<5, no swap

3 4 5 1 12

5>1, so they are swapping positions

3 4 1 5 12

5<12, no swap

3 4 1 5 12

Third Pass

3 4 1 5 12

3<4, no swap

3 4 1 5 12

4>1, so they are swapping positions

3 1 4 5 12

4<5, no swap

3 1 4 5 12

5<12, no swap

3 1 4 5 12

Fourth Pass

1 3 4 5 12

1<3, so they are swapping positions

If you see carefully u can see the array is sorted in ascending order (small to big).

Performance:

Worst case performance O (n2)

Best case performance O (n)

Here is the java code for bubble sort.


//Author : S.Mahbub - uz - zaman

//Bubble Sort for 5 integer numbers

import java.util.*;

public class BubbleSort{

    public static void main (String [] args){

        Scanner sc = new Scanner (System.in);

        int temp;

        int array[]= new int[5];

        for(int i=0;i<5;++i){

           array[i]=sc.nextInt();

        }

        for(int x=1; x
            for(int y=0; yarray[y+1]){

                   temp = array[y+1];

                   array[y+1] = array[y];

                   array[y] = temp;

                }

            }

        }

        for(int i=0; i<array.length;++i)
           System.out.println(array[i]);
    }

}

Facts

1. If you see very carefully you can notice that after each pass the biggest number is in the last position

2. When the number is already sorted, in bubble sort we keep doing the work.

3. If there are 5 number the probability of best case is 1/5. But if you see the previous code we are comparing unnecessary things and if the user gives sorted array we are also doing the work.So for best and worst case we are doing same work. So here is a modified version which handle the best case and also do not compare unnecessarily . And also do not continue the comparisons for following example

1 2 3 12 4

Only after one pass the number will sorted so we don’t need to compare any more.

Here is the code

//Author : S.Mahbub - uz - zaman

//Bubble Sort for 5 integer number

import java.util.*;

public class BubbleSortModifiedVersion{

     public static void main (String [] args){

          Scanner sc = new Scanner (System.in);

          int temp;

          int array[]= new int[5];

          boolean stop= false;

//we are assuming the data is already sorted

          for(int i=0;i<5;++i){

              array[i]=sc.nextInt();

          }

          int size = array.length-1;

          for(int x=1; x
              for(int y=0; yarray[y+1]){

                    temp = array[y+1];

                    array[y+1] = array[y];

                    array[y] = temp;

                    stop=true;
//enter if block means data is not sorted yet
                  }

              }

              --size;

              if(stop==false){
//means the data is sorted

                break;

              }

              stop= false;
//we are assuming that data is sorted

/* so at the end of the first comparisons we know that
the biggest number is in the last */

          }
//so we don't need to compare the last number again

          for(int i=0; i<array.length;++i)
             System.out.println(array[i]);

     }

}

So this is all about bubble sort :).

Advertisements

2 thoughts on “Bubble Sort

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s