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.