**Sorting an Array with a
Bubble Sort**

Introduction.
Another classic problem in the computer sciences is
sorting. It is possible to think of plenty of applications
of searching such as the following.
Obviously, these sorts of scenarios are endless. So, you should be able to see that quickly and efficiently being able to find the desired information is very important. If it takes too long then it delays all kinds of other things that may be more important. This next applet will randomly generate an array of size 10 of integers from 1 to 100. Then this array will be sorted in ascending order.
We will use an approach called a
I think it will be much easier to discuss the code after seeing an example and describing the bubble sort process in words. This applet is a modification of one of the same name in
Deitel and Deitel. The major modification is to display the
intermediate steps in the sorting process so we can discuss them.
The program should be called |

import java.awt.*;import javax.swing.*; public class BubbleSort extends JApplet { String output = "Data items in original order\n"; int a[]; public void init() { JTextArea outputArea = new JTextArea(); Container c = getContentPane(); c.add(outputArea); a = new int[10]; // randomly generate an array of 10 integers // between 1 and 100 to be sorted for (int i = 0; i < a.length; i++) a[i] = 1 + (int) (Math.random() * 100); // display the original ordering of the array for (int i=0; i < a.length; i++) output = output + " " + a[i]; bubblesort( a ); // display the final ordering after bubble sort is completed output = output + "\n\nData items in ascending order\n"; for (int i=0; i < a.length; i++) output = output + " " + a[i]; outputArea.setText(output); } // sort the elements of an array with a bubble sort public void bubblesort( int b[] ) { int passThrough; // loop for number of times to pass through array for (int pass = 0; pass < b.length; pass++) { // loop to actually pass through the array // and swap adjacent pairs of numbers if appropriate for (int i=0; i < b.length - 1; i++) // swap if i-th entry is greater than i+1-st entry if (b[i] > b[i+1]) swap(b, i, i+1); // section of code to display the results // of the sort after each pass passThrough = pass + 1; output = output + "\n\nOrder after pass " + passThrough + "\n"; for (int i=0; i < b.length; i++) output = output + " " + b[i]; } } // swap two elements of an array public void swap( int c[], int first, int second) { int hold; hold = c[first]; c[first] = c[second]; c[second] = hold; } } |

Notice, we have done a fairly minimal implementation
with no error trapping and a flow layout. Since the size of the
applet window impacts the display it is given below in
BubbleSort.html. |

<html><applet code="BubbleSort.class" width=220 height=600> </applet> </html> |

I ran the program to generate the following display for our discussion. But your results will almost surely differ due to the random number generation. Fortunately, you should be able to understand some basic operating principles in the code before examining it. |

Notice the initial array of randomly generated integers from 1 to 100 is 53 31 56 9 37 1 1 97 14 56 Notice how we actually have some recurrences of numbers in this small array. What this implies about random number generation is beyond the scope of this course. Take some time to think how you would want to sort these in order from lowest to highest and remember you need to write code to do it. A bubble sort works on the basic principle of
Describing this in more detail, let's talk
about how this array was sorted. This sequence of steps as a whole
will be called a
Notice how this corresponds to the list that appears in the applet window after the first pass. You should also notice
This is why this is called a bubble sort. The higher numbers sort of bubble up. the lower numbers sort of bubble down. The second pass will work similarly. I won't present it, but you should notice how the next highest number bubbles up to the second to the last entry and how some other numbers bubble up and others bubble down in the swap. You should also be able to see that we need to take as many passes as there are elements in the array in order to make certain everything has bubbled to the correct relative position.
You can play with this all you want. |