Java Bubble Sort Programs

Normal Bubble Sort Program

[java]// Main Method

import java.io.DataInputStream;
class bubble1
{
public static void main ( String args[] )
{
int i, n=0;
int x[] = new int [25];
DataInputStream in = new DataInputStream(System.in);

try
{
System.out.print("Enter how many numbers to be sorted : ");
n = Integer.parseInt(in.readLine());
System.out.println("Enter "+n+" Elements in any order: ");
for(i=0; i<n; i++)
{
System.out.print(" Element x["+(i+1)+"]=");
x[i]=Integer.parseInt(in.readLine());
}
}

catch(Exception e) { }

bubble(x,n);

System.out.println("nSorted elements are: ");
for(i=0; i<n; i++)
{
System.out.println(" Element x["+(i+1)+"]="+x[i]);
}
}

// Bubble Sort Method

static void bubble (int x[], int n)
{
int hold, j, pass;
for(pass=0; pass<n-1; pass++)
{
// outer loop controls the number of passes
for(j=0; j<n-1; j++)
{
// inner loop governs each individual pass
if ( x[j] > x[j+1] )
{
// interchange elements if they are out of order
hold = x[j];
x[j] = x[j+1];
x[j+1] = hold;
}
}
}
System.out.println("nNumber of passes: " + pass);
}
}[/java]

Output

Revised Bubble Sort Program

[java]

//————————————————————————————
// Main Method

import java.io.DataInputStream;
class bubble2
{
public static void main ( String args[] )
{
int i, n=0;
int x[] = new int [25];
DataInputStream in = new DataInputStream(System.in);

try
{
System.out.print("Enter how many numbers to be sorted : ");
n = Integer.parseInt(in.readLine());
System.out.println("Enter "+n+" Elements in any order: ");
for(i=0; i<n; i++)
{
System.out.print(" Element x["+(i+1)+"]=");
x[i]=Integer.parseInt(in.readLine());
}
}

catch(Exception e) { }

bubble(x,n);

System.out.println("nSorted elements are: ");
for(i=0; i<n; i++)
{
System.out.println(" Element x["+(i+1)+"]="+x[i]);
}
}

//————————————————————————————
// Bubble Sort Method

static void bubble (int x[], int n)
{
int hold, j, pass;
boolean SWITCHED = true;
for(pass=0; (pass<n-1) && (SWITCHED==true); pass++)
{
// outer loop controls the number of passes
SWITCHED = false;
for(j=0; j<n-1; j++)
{
// inner loop governs each individual pass
if ( x[j] > x[j+1] )
{
// interchange elements if they are out of order
SWITCHED = true;
hold = x[j];
x[j] = x[j+1];
x[j+1] = hold;
}
}
}
System.out.println("nNumber of passes: " + pass);
}
}

[/java]

Theory

In case of sorting the array in ‘Ascending Order’ : The idea of bubble sort is to compare every element (i) with the ‘next’ element (i+1) in the array and bubble out the largest element to the ‘end’ of that array. The normal bubble sort helps us to do that, but there are some obvious improvements which can be done in it. Hence there is a need of revised bubble sort. The revised bubble sort helps to save us time by adding two main conditions.

The first improvement in bubble sort was to add a switched variable. To check whether the array is ‘already’ sorted or not. If the array is already sorted then we need not add anymore passes.

The second improvement was implemented by this part of the code n-pass-1. This filters out the ‘already’ bubbled out elements from the next passes. Example: If a element is bubbled out to the end of the array in n th pass.

This element wont be considered in the n+1 th pass.
Thus saving us a huge amount of time, especially if the array is quite big.

Leave a Reply