Thursday, 25 June 2015

Bubble Sort with example and Java Program

The Bubble sort is a exchange sorting Technique. It sort the array of elements by comparing each adjacent element with another, if they are in wrong order they can be arranged in the order. This process continues all the elements are  get sorted. If you have 'n' elements the there are 'n-1' iterations are needed to sort the array of elements.


Why it is called as "Bubble Sort "?


                                                           The exchange sort is called as bubble sort because, we are bubbling or selecting each time one element to  compare with other element until all the elements are get sorted.For example if you have the Following elements: 5,1,4,2,8 and the Bubble Sort works like this

Initial Arrays is

5,1,4,2,8        and we start comparison by  selecting a reference

  1.  5,1,4,2,8 -Here we are comparing 5 and 1, since 5 is greater than 1, and we rearrange them as. That is swap the positions
  2.  
  3.  1,5,4,2,8  ----Now comparing 5 and 4,swap them since 5is greater than4 as
  4.   1,4,5,2,8 -----Swap 5 and 2
  5.   1,4,2,5,8
Repeat the above process and after sorting array once again scan the arrays to complete the process.


The Following is the Bubble sort implementation in java

import java.util.Scanner;
 
class BubbleSortDemo {
  public static void main(String []args) {
    int n, c, d, swap;
    Scanner in = new Scanner(System.in);
 
    System.out.println("Input number of integers to sort");
    n = in.nextInt();
 
    int array[] = new int[n];
 
    System.out.println("Enter " + n + " integers");
 
    for (c = 0; c < n; c++) 
      array[c] = in.nextInt();
 
    for (c = 0; c < ( n - 1 ); c++) {
      for (d = 0; d < n - c - 1; d++) {
        if (array[d] > array[d+1]) /* For descending order use < */
        {
          swap       = array[d];
          array[d]   = array[d+1];
          array[d+1] = swap;
        }
      }
    }
 
    System.out.println("Sorted list of numbers");
 
    for (c = 0; c < n; c++) 
      System.out.println(array[c]);
  }
}



Nothing is done in the above program, we are comparing the two elements and swap them and are stored in the temp array.

The bubble sort have the complexity of  O(n) in Best case, O(n2) in both Average and Worst case.

0 comments:

Post a Comment

Scribe to Youtube Channel

Advertisement

Find Us On Facebook

C Programming

More

C++ Tutorial

More

Java Tutorial

More

software engineering

More

MS Office

More

Database Management

More
Top