09 April 2012

Implement a Bubble Sort


Algorithm


Bubble sort consists of comparing each pair of adjacent items. Then one of those two items is considered smaller (lighter) and if the lighter element is on the right side of its neighbor, they swap places. Thus the lightest element bubbles to the surface and at the end of each iteration it appears on the top. I’ll try to explain this simple principle with some pictures.

1. Each two adjacent elements are comparedIn bubble sort we've to compare each two adjacent elements


In bubble sort we've to compare each two adjacent elements
Here “2″ appears to be less than “4″, so it is considered lighter and it continues to bubble to the surface (the front of the array).

2. Swap with heavier elements

If heavier elements appear on the way we should swap them

If heavier elements appear on the way we should swap them
On his way to the surface the currently lightest item meets a heavier element. Then they swap places.

3. Move forward and swap with each heavier item

Swapping is slow and that is the main reason not to use bubble sort

Swapping is slow and that is the main reason not to use bubble sort
The problem with bubble sort is that you may have to swap a lot of elements.

4. If there is a lighter element, then this item begins to bubble to the surface

We can be sure that on each step the algorithm bubbles the lightest element so far

We can be sure that on each step the algorithm bubbles the lightest element so far
If the currently lightest element meets another item that is lighter, then the newest currently lightest element starts to bubble to the top.

5. Finally the lightest element is on its place


Finally the list begins to look sorted

Finally the list begins to look sorted
 
At the end of each iteration we can be sure that the lightest element is on the right place – at the beginning of the list.
The problem is that this algorithm needs a tremendous number of comparisons.





import java.util.*;
public class BubbleSort {
public static void main(String[] args) {
int intArray[]=new int[6];
Scanner input = new Scanner(System.in);
for(int i = 0; i<5; i++)
{
System.out.println("Enter the number");
intArray[i] = input.nextInt();
}
System.out.println("Array Before Bubble Sort");
for(int i=0; i < intArray.length; i++){
System.out.print(intArray[i] + " ");
}
bubbleSort(intArray);
System.out.println("");
System.out.println("Array After Bubble Sort");
for(int i=0; i < intArray.length; i++){
System.out.print(intArray[i] + " ");
}
}
private static void bubbleSort(int[] intArray) {

int n = intArray.length;
int temp = 0;
for(int i=0; i < n; i++){
for(int j=1; j < (n-i); j++){
if(intArray[j-1] < intArray[j]){
temp = intArray[j-1];
intArray[j-1] = intArray[j];
intArray[j] = temp;
}
}
}
}
}

1 comments:

Naviya Nair said...

I have read your blog its very attractive and impressive. I like it your blog.

Java Online Training Java EE Online Training Java EE Online Training Java 8 online training Core Java 8 online training

Java Online Training from India Java Online Training from India Core Java Training Online Core Java Training Online Java Training InstitutesJava Training Institutes

Post a Comment

Related Posts with Thumbnails

Popular Posts

 
;