BUBBLE SORT

Sorting Algorithms are concepts that every competitive programmer must know. Sorting algorithms can be used for collections of numbers, strings, characters, or a structure of any of these types.

Bubble sort is based on the idea of repeatedly comparing pairs of adjacent elements and then swapping their positions if they exist in the wrong order.

Assume that A[ ] is an unsorted array of n elements. This array needs to be sorted in ascending order. The pseudo code is as follows:

Lets try to understand the pseudo code with an example: 

A [4] = { 7, 4, 5, 2}

In step 1, 7 is compared with 4. Since 7>4, 7 is moved ahead of 4. Since all the other elements are of a lesser value than 7, 7 is moved to the end of the array.

Now the array is A[]={4,5,2,7}.

In step 2, 4 is compared with 5. Since 5>4 and both 4 and 5 are in ascending order, these elements are not swapped. However, when 5 is compared with 2, 5>2 and these elements are in descending order. Therefore, 5 and 2 are swapped.

Now the array is A[]={4,2,5,7}.

In step 3, the element 4 is compared with 2. Since 4>2 and the elements are in descending order, 4 and 2 are swapped.

The sorted array is A[]={2,4,5,7}.

Complexity:

The complexity of bubble sort is O(n2) in both worst and average cases, because the entire array needs to be iterated for every element.

Program for BUBBLE SORT 

import java.util.Scanner;
class bubblesort
 {
  public static void main(String[] args)
  {
   int i,j,n,temp;
   Scanner bs = new Scanner(System.in);
   System.out.println("Enter Size Of Array :");
   n=bs.nextInt();
   int[] a;//declaration of array
   a=new int[n]; // Creation of array with given size
   System.out.println("Enter unsorted Array :");
   for(i=0;i<n;i++)
    {
     System.out.printf("\n Element a[%d]  :",i);
     a[i]=bs.nextInt();
    }
   System.out.print("\n Unsorted Array elements :");
   for(i=0;i<n;i++)
     {
      System.out.print( a[i] +" ");
     }
   for(i=0;i<n;i++)
    {
     System.out.printf("\n ADDRESS=%h ---- ARRAY=a[%d]----- DATA=%d --- location=%d\n",i*4,i,a[i],i+1);
    }
   for(i=0;i<n-1;i++)
    {
     for(j=0;j<n-1-i;j++)
      {
        if(a[j]>a[j+1])
        {
         temp=a[j];
         a[j]=a[j+1];
         a[j+1]=temp;
        }
      }
    }
   System.out.print("\n Sorted Array elements :");
   for(i=0;i<n;i++)
     {
      System.out.print( a[i] +" ");
     }

   for(i=0;i<n;i++)
    {
     System.out.printf("\n ADDRESS=%h ---- ARRAY=a[%d]----- DATA=%d --- location=%d\n",i*4,i,a[i],i+1);
    }
  }
}



output