Bubble sort algorithm, flow chart, analysis and Java program

Friday, September 04, 2009

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.

3 comments:

  1. thank you..it's a big help for me and to my fellow programming students...god bless !

    ReplyDelete
  2. where is the flowchart

    ReplyDelete
  3. where is the flowchart?

    ReplyDelete