The Bubble Sort Algorithm

 

Algorithm Description

This is one of the simpler sorting algorithms, and typically the first or the second sorting algorithm studied. 

 

Lets say there is an array of n itegers. the name of the array is a[]. Then the bubble Sort Algorithm will be as follows.

 

 

 

 

                    for (int i = 0; i < a.length ; i++) {

                            for (int j = a.length-1; j>i ; j--){

                                    if (a[i-1] > a[i]){

                                        int temp = a[i];

                                        a[i] = a[i-1];

                                        a[i-1] = temp;

                                    }

                            }

                        }

 


Instructions on the use of the Applet :

 

The applet has four sections. The top section  Contains a button labeled " Start Sorting " . 

On initialization the applet generates ten random numbers. The numbers are limited from 0 to 99. The applet then waits for the user to press the 

start Sorting button. When the button is pressed the animation starts.

The second section from the top of the applet contains two lines. These lines indicates the count of the  two variable i and j of the two loops at any time.

The third section from the top of the applet contains the code of the bubble sort. When the applet is running a yellow bar indicates the current position of the program.

The bottom section contains the graphic representation of the array and its elements and the position of those elements at certain time. 

 


 

The Applet

 

 


Complexity of the Algorithm

Bubble Sort makes at most (n-1) passes over the data. The first pass compares (n-1) pairs of elements and results in the smallest element moving to the first position of the array. The second pass works on the remaining (n-1) element array and hence makes (n-2) comparisons.

Thus, in the worst case bubblesort algorithm makes

(n-1)+(n-2) + . . . . . . . .+2+1 = n*(n-2)/2=O(n2)

The Bubble Sort is an O(n2) algorithm.


This page was created on May 10, 2001 by Mohammad Khurshid Ali.
This page was updated with minor formatting changes on April 26, 2002 by Brent Petersen .

© Copyright 2001-2004, Mohammad Khurshid Ali. UNB Professional Page Disclaimer