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. organizing grades for a course in descending order by their overall score organizing clients by the amount of money they've spent with your firm ordering potential students to be considered for financial aid by their total SAT score finding the physicians on your sales call list that you haven't visited and order them by how long it has been since you have visited   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 bubble sort because of how numbers bubble to the top of the list.  Rather than discuss this in the abstract we will first develop the code run the program examine the output discuss the steps that are taken to sort the array discuss the code 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 BubbleSort.java.

 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.



 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.