## 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 = trueEND`

## 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.