Bubble sort

Bubble sort is a simple and common sorting algorithm. It sorts by iterating through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. This process will be continued until all the elements are being sorted i.e.; no swapping is required in the list.
Bubble sort name came for this algorithm due to - like a bubble comes to the top of the water, each iteration will push one smaller element to the top of the list (if the algorithm is for ascending order).

Performance

Bubble sort is not the efficient algorithm in terms of the performance because its worst-case and average complexity both ?(n2), where n is the number of items being sorted.

Algorithm


START
DECLARE n, list
ACCEPT n
ACCEPT n values into an array list
DO
swapped := false;
FOR EACH i IN 0 to n-1
LOOP
IF list[i] > list[i+1] THEN
temp := list[i]
list[i]:=list[i+1]
list[i+1]:=temp
END IF
END LOOP
WHILE swapped = true
END

Java program


import java.io.*;

/**
* This class demonstrates the bubble sort.
* @author SANTHOSH REDDY MANDADI
* @version 1.0
* @since 04th September 2009
*/
public class BubbleSort
{
public static void main(String[] args) throws Exception
{
int values[]=new int[5];
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
System.out.println("Enter "+values.length+" values to sort using bubble sort");
for(int i=0;i<values.length;i++)
{
try{
values[i]=Integer.parseInt(br.readLine());
}catch(NumberFormatException e)
{
e.printStackTrace();
values[i]=0;
}
}
bubbleSort(values);
for(int i=0;i<values.length;i++)
{
System.out.print(values[i]+" ");
}
}

/**
* This method will sort the passed array
* @author SANTHOSH REDDY MANDADI
* @since 4-Sep-2009
* @param an array of the list of values to be sorted
*/
public static void bubbleSort(int[] values)
{
boolean swapped=false;
do
{
//When initializing the each loop assing false to swapped flag
swapped = false;
//Looping through the list
for(int i=0; i<values.length-1; i++)
{
//Comparing the adjecent elements
if(values[i]>values[i+1])
{
//Swapping
int temp=values[i];
values[i]=values[i+1];
values[i+1]=temp;
//Swapped is true
swapped=true;
}
}
}while (swapped);
}
}

Explanation:

Let us consider we've executed the above program by inputting the values (43, 25, 21, 56, 4). Here is how the list will be modified in each iteration.
swapped value = false

First iteration:

43 25 21 56 4 25 43 21 56 4 - swapped since 43 > 25
25 43 21 56 4 25 21 43 56 4 - swapped since 43 > 21
25 21 43 56 4 25 21 43 56 4 - not swapped since 43 < 56
25 21 43 56 4 25 21 43 4 56 - swapped since 54 > 4

Second iteration:

25 21 43 4 56 21 25 43 4 56
21 25 43 4 56 21 25 43 4 56
21 25 43 4 56 21 25 4 43 56
21 25 4 43 56 21 25 4 43 56

Third iteration:

21 25 4 43 56 21 25 4 43 56
21 25 4 43 56 21 4 25 43 56
21 4 25 43 56 21 4 25 43 56
21 4 25 43 56 21 4 25 43 56

Fourth iteration:

21 4 25 43 56 4 21 25 43 56
4 21 25 43 56 4 21 25 43 56
4 21 25 43 56 4 21 25 43 56
4 21 25 43 56 4 21 25 43 56

Fifth iteration:

4 21 25 43 56 4 21 25 43 56
4 21 25 43 56 4 21 25 43 56
4 21 25 43 56 4 21 25 43 56
4 21 25 43 56 4 21 25 43 56
Since there're no swaps happened in the fifth operation, the outer loop will be stopped since the condition swapped = true false.

Above program has been tested in JDK 1.4, 1.5, and 1.6.

Click here to check out other programs that I've developed.