Home : Course Map : Chapter 8 : Java : Tech :
Sorting
JavaTech
Course Map
Chapter 8

Introduction
Threads Overview
  Demo 1   Demo 2
Stopping Threads
Multi-Processing
Thread Tasks
Animations
 
 Demo 3   Demo 4  
  Demo 5

Non-interacting
  Demo 6

Task Splitting
  Demo 7

Exclusivity
  Demo 8

Communicating
  Demo 9

Priority/Scheduling
More Thread

Exercises

    Supplements
Java2D Animation
  Demo 1 
Processor View
More Concurrency
Cloning
  Demo 2  Demo 3 

     About JavaTech
     Codes List
     Exercises
     Feedback
     References
     Resources
     Tips
     Topic Index
     Course Guide
     What's New

Technical applications frequently require sorting of data such as arranging an array of numerical values in ascending or descending order. The Java 2 SE comes with several sorting tools that work with both primitive numerical arrays and also with arrays and collections of objects.

We will combine sorting and threading to create a fun demonstration with an animation of sorting a histogram bin distribution.

Numerical Sorting

The java.util.Arrays class (discussed also in Chapter 10: Java : Arrays) comes with several overloaded versions of its static sort() method for sorting arrays of primitive numerical types:

  • void sort(byte[] a)
  • void sort(short[] a)
  • void sort(char[] a)
  • void sort(int[] a)
  • void sort(float[] a)

The values are sorted into ascending order for the entire array for these single argument sort() methods. The methods:

  • void sort(byte[] a, int fromIndex, int toIndex)
  • void sort(short[] a, int fromIndex, int toIndex)
  • void sort(char[] a, int fromIndex, int toIndex)
  • void sort(int[] a, int fromIndex, int toIndex)
  • void sort(double[] a, int fromIndex, int toIndex)

arrange in ascending order the array elements between and including fromIndex and up to but not including toIndex. A version of QuickSort (see below) is used.

Object Sorting

Object sorting touches on the big topic of Java Collections where a collection is defined as "an object that represents a group of objects." We briefly discuss the Collections Framework in Chapter 10. It encompasses an extensive set of interfaces and classes to create several varieties of sets, lists, and maps of objects.

For our sorting task here we note two interfaces in the collections framework:

  • Comparable interface - includes one method:

    • int compareTo(Object o) - Returns a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second.

  • Comparator interface - includes two methods:

    • int compare(Object o1, Object o2) - Returns a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second according to the ordering rule for the objects.

    • boolean equals(Object obj) - returns true if obj also implements Comparator and provides the same ordering as this one.

These allow one to create a sorting rule for any time of class.

Instances of a class in an array can be ordered with the Arrays methods:

  • void sort(Object[] a)
  • void sort(Object[] a, int fromIndex, int toIndex)

if the instances implement Comparable. A number of core Java classes such as the primitive type wrappers implement Comparable.

If the class(es) of objects that you want to sort do not implement Comparable then you can create a Comparator for them and then use the Arrays methods:

  • void sort(Object[] a, Comparator c)
  • void sort(Object[] a, int fromIndex, int toIndex, Comparator c)

where you supply the relevant Comparator implementation.

Note that the Collections class also includes two static sort methods for objects that implement the List interface such as Vector:

  • void sort(List list) - where items in the List class must implement the Comparable interface.
  • void sort(List list, Comparator c)

Sorting Histogram

Many computer science texts discuss sorting algorithms so we will not delve into the details of particular algorithms such as the Quick Sort (see references). Instead we will use sorting to provide another illustration of threading.

In the demo program below, we could use the Arrays sort() methods above to sort the bins but instead we created an abstract Sorter base class and a concrete subclass example that allows for an animation of the sorting. After the histogram filling finishes, the "Sort" button will initiate the sorting of the bins in ascending order from left to right. (In the next section we use the sort() method in the Arrays class to determine the median of a data array.)

The sort() method in the BubbleSorter class calls back to the applet parent after each step in the sorting and tells it to update the histogram display. The sorting pauses after each step, otherwise the sorting would go too fast to see on most modern processors.

The Sorter extends Thread and thus allows the sorting to be "spun off" from the actionPerformed() method, which returns to the event handling thread. Otherwise, the the user interface would freeze while waiting for the sorting to finish.


SortHistFillApplet.java - the applet/app class to operate the sorting interface. Similar to the AdaptHistFillApplet class except for adding a "Sort" button and extra code in the update() and done() methods to handle call backs from the sorter.

+ New classes:
BubbleSorter.java - this subclass of Sorter implements the simple bubble sort method. It provides a sort method for both integer and double arrays. It also provides the run() method for threading. After each step it calls back to the owner via the Updateable interface method update(). It also calls the done() method after it finishes the sort.

Sorter.java - abstract base class for sorter algorithm classes. Extends Thread so that the sorting can be done as a separate process.

+ Previous classes:
Chapter 8:Tech: HistogramAdapt.java,
Chapter 8:Tech: MakeData.java, Updateable.java
Chapter 7:Tech:
HistogramStat.java,
Chapter 6:Tech: Histogram.java, HistPanel.java
Chapter 6:Tech: PlotPanel.java, PlotFormat.java

/**
  * An abstract class used as a base class for
  * sort algorithm classes.
**/
public abstract class Sorter extends Thread
{
  boolean fStop = false;
  Updateable fOwner = null;
  int [] fIdata = null;
  double [] fDdata = null;

  public void setStop ()
  { fStop = true;}

  public abstract void sort (int data[]);
  public abstract void sort (double data[]);

} // class Sorter

/**
  * Use a simple Bubble Sort to sort either an integer
  * or double array. Extends abstract Thread subclass Sorter
  * so it provides a run () method.
 **/
public class BubbleSorter extends Sorter
{

  /** Sort integer data array. **/
  public BubbleSorter (Updateable owner, int [] data) {
    fOwner = owner;
    fIdata = data;
  } // ctor

  /** Sort double data array. **/
  public BubbleSorter (Updateable owner, double [] data) {
    fOwner = owner;
    fDdata = data;
  } // ctor

  public void run () {
    if (fIdata != null)
        sort (fIdata);
    else
        sort (fDdata);
  } // run

  /** Sort an int array. **/
  public void sort (int data[]) {
    for (int i = data.length-1; i >= 0 ; i--) {
        boolean swapped = false;
        for (int j = 0; j < i; j++) {
            if (fStop) {
                fOwner.done ();
                return;
            }
            if (data[j] > data[j+1]) {
                int tmp = data[j];
                data[j] = data[j+1];
                data[j+1] = tmp;
                swapped = true;
            }
            fOwner.update (this);
        }
        if  (!swapped) break;
    }
    fOwner.done ();

  } // sort (int data [])

  // Sort a double array. **/
  public void sort (double data[]) {
    for (int i = 0; i < data.length; i++) {
        boolean swapped = false;
        for (int j = 0; j < i; j++) {
            if (fStop) {
                fOwner.done ();
                return;
            }
            if ( data[j] > data[j+1]) {
            double tmp = data[j];
            data[j] = data[j+1];
            data[j+1] = tmp;
            swapped = true;
        }
        fOwner.update (this);
      }
      if  (!swapped) break;
    }
    fOwner.done ();
  } // sort (double data [])

} //class BubbleSorter

import javax.swing.*;
import java.awt.*;
import java.awt.event.*;

/**
  * Demonstrate Java sorting tools by applying them to histogram
  * bin values.
  *
  * This program will run as an applet inside an application frame.
  *
  * The applet uses the HistPanel to display contents of
  * an instance of Histogram. HistFormat used by HistPanel to
  * format the scale values.
  *
  * The java.util.Timer and java.util.TimerTask are used
  * to update the display of the histogram during the filling
  * of the histogram.
  *
  * Includes "Go" button to initiate the filling of the histogram.
  * To simulate data taking, a combination of a Gaussian and random
  * background values are generated.
  *
  * The number of values taken from
  * entry in a JTextField. "Clear"  button clears the histogram.
  * In standalone mode, the Exit button closes the program.
  *
  *
**/
public class SortHistFillApplet extends JApplet
             implements ActionListener, Updateable
{
  // Use the HistPanel JPanel subclass here
  HistPanel fOutputPanel;

  Histogram fHistogram;
  int fNumDataPoints = 100;

  boolean fMakingHist   = false;
  boolean fUpdateDisplay = false;
  MakeData fMakeData;

  // Use the java.util Timer and TimerTask combo
  // for timing events.
  java.util.Timer fTimer;

  // Reference to sorting object.
  Sorter fSorter;

  // A text field for input strings
  JTextField fTextField = null;

  // Flag for whether the applet is in a browser
  // or running via the main () below.
  boolean fInBrowser = true;

  //Buttons
  JButton fGoButton;
  JButton fSortButton;
  JButton fClearButton;
  JButton fExitButton;

  /**
    * Create a User Interface with a histogram and a Go button
    * to initiate processing and a Clear button to clear the .
    * histogram. In application mode, the Exit button stops the
    * program.
   **/
  public void init () {
    Container content_pane = getContentPane ();

    JPanel panel = new JPanel (new BorderLayout ());

    // Use a textfield for an input parameter.
    fTextField =
      new JTextField (Integer.toString (fNumDataPoints), 10);

    // If return hit after entering text, the
    // actionPerformed will be invoked.
    fTextField.addActionListener (this);

    fGoButton = new JButton ("Go");
    fGoButton.addActionListener (this);

    fSortButton = new JButton ("Sort");
    fSortButton.addActionListener (this);

    fClearButton = new JButton ("Clear");
    fClearButton.addActionListener (this);

    fExitButton = new JButton ("Exit");
    fExitButton.addActionListener (this);

    JPanel control_panel = new JPanel ();

    control_panel.add (fTextField);
    control_panel.add (fGoButton);
    control_panel.add (fSortButton);
    control_panel.add (fClearButton);
    control_panel.add (fExitButton);

    // Create a histogram and start filling it.
    makeHist ();
    fGoButton.setText ("Stop");
    fClearButton.setEnabled (false);
    fSortButton.setEnabled (false);
    if (fInBrowser) fExitButton.setEnabled (false);

    // JPanel subclass here.
    fOutputPanel = new HistPanel (fHistogram);

    panel.add (fOutputPanel,"Center");
    panel.add (control_panel,"South");

    // Add text area with scrolling to the contentPane.
    content_pane.add (panel);
  } // init

  public void actionPerformed (ActionEvent e) {
    Object source = e.getSource ();
    if (source == fGoButton || source == fTextField )  {
        String strNumDataPoints = fTextField.getText ();
        try {
          fNumDataPoints = Integer.parseInt (strNumDataPoints);
        }
        catch (NumberFormatException ex) {
          // Could open an error dialog here but just
          // display a message on the browser status line.
          showStatus ("Bad input value");
          return;
        }
        if (!fMakingHist) {
            makeHist ();
            fGoButton.setText ("Stop");
            fSortButton.setEnabled (false);
            fClearButton.setEnabled (false);
        }  else {
            // Stop button has been pushed
            fGoButton.setText ("Go");
            fSortButton.setEnabled (true);
            fClearButton.setEnabled (true);
            fMakingHist = false;
        }

    } else if (source == fSortButton) {
        if (fSorter == null) {
            fSortButton.setText ("Stop");
            fGoButton.setEnabled (false);
            fClearButton.setEnabled (false);

            fSorter = new BubbleSorter (this, fHistogram.getBins ());
            fSorter.start ();

        } else  { // Stop button pushed
            fSorter = null;
            fSortButton.setText ("Sort");

            fGoButton.setEnabled (true);
            fClearButton.setEnabled (true);
        }
    } else if (source == fClearButton) {
        fHistogram.clear ();
        repaint ();

    } else if (!fInBrowser)
        System.exit (0);

  } // actionPerformed

  /**
    *  Create the histogram, create the MakeData instance and
    *  spin it off in a thread. Set up a java.util.Timer to
    *  run the PaintHistTask periodically.
   **/
  void makeHist () {
    if (fMakingHist) return; // only fill one hist at a time.
        fMakingHist = true;

    // Create an instance of the histogram class.
    // Make it wide enough enough to include the data.
    if (fHistogram == null)
        fHistogram = new Histogram ("Gaussian + Random Background",
                                "Data",
                                20,-10.0,10.0);

    // Create the runnable object to fill the histogram
    // Center signal at 3.0 and create background between
    // -10 and 10. The fraction of the data due to the
    // Gaussian will be 0.60. The maximum delay between
    // data poins will be 500msecs.
    fMakeData =
      new MakeData (this, fHistogram, fNumDataPoints,
                   3.0, 0.60, -10.0, 10.0, 500);
    Thread data_thread = new Thread (fMakeData);

    // Before starting the filling, create the timer task
    // that will cause the histogram display to update
    // during the filling.
    // Create a timer. TimerTask created in MakeHist ()
    fTimer = new java.util.Timer ();

    // Start the timer after 100ms and then repeat calls
    // to run in PaintHistTask object every 250ms.
    fTimer.schedule (new PaintHistTask (), 100, 250);

    // Now start the data filling.
    data_thread.start ();

  } // makeHist

  /**
   * Use the inner class technique to define the
   * TimerTask subclass for signalling that the display
   * should be updated.
   */
  class PaintHistTask extends java.util.TimerTask
  {
    public void run () {
       fUpdateDisplay = true;
    }
  } // class PaintHistTask

  /**
   *  Repaint the histogram display. If called by
   *  the MakeData object, it will turn off the
   *  update display flag and return the fMakingHist flag
   *  to indicate if updating should continue.


   *  If called by a Sorter object, it will repaint the
   *  panel and the pause briefly so that the display
   *  will give a nice animation of the sorting.
   */
  public boolean update (Object obj) {
    // For sorting, always repaint the output.
    if (obj instanceof Sorter) {
        fOutputPanel.repaint ();
        try {
          Thread.sleep (25);
        }
        catch (InterruptedException e)
        {}
        return true;
    }

    // Don't update the display until the timer
    // turns on the fUpdateDisplay flag.
    if (fUpdateDisplay) {
      // Possible this method called before fOutputPanel
      // created in the init (). So check if it exists
      // before attempting to repaint.
      if (fOutputPanel != null) {
          fOutputPanel.getScaling ();
          fOutputPanel.repaint ();
      }
      fUpdateDisplay = false;
    }
    return fMakingHist;
  } // update

  /**
    *  Called when the histogram filling is finished
    *  and when the sorting is finished.
   **/
  public void done () {
    fMakingHist = false;
    fSorter = null;

    // Stop the histogram display updates.
    fTimer.cancel ();

    // Update one last time
    fOutputPanel.getScaling ();
    fOutputPanel.repaint ();

    // Reset the buttons.
    fGoButton.setText ("Go");
    fSortButton.setText ("Sort");

    fGoButton.setEnabled (true);
    fSortButton.setEnabled (true);
    fClearButton.setEnabled (true);

  } // done

  public static void main (String[] args) {
    //
    int frame_width=450;
    int frame_height=300;

    //
    SortHistFillApplet applet = new SortHistFillApplet ();
    applet.fInBrowser = false;
    applet.init ();

    // Following anonymous class used to close window & exit program
    JFrame f = new JFrame ("Demo");
    f.setDefaultCloseOperation (JFrame.EXIT_ON_CLOSE);

    // Add applet to the frame
    f.getContentPane ().add ( applet);
    f.setSize (new Dimension (frame_width,frame_height));
    f.setVisible (true);
  } // main
} // class SortFillHistApplet

 

Note that java.util.Arrays also provides other useful methods. If you need to search through a large array for a particular numerical value it provides binary search methods for different types of arrays. A binary search method requires that you first sort the array in ascending order. It also provides methods to fill arrays with a given value.

See the following references for more about sorting in Java and in general.

References/Resources

Last update: Nov. 18, 2004

              Tech
Timers
  Demo 1
Hist. Adapt Range
  Demo 2
Sorting in Java
  Demo 3
Histogram Median
  Demo 4
Refactoring
  Demo 5
Error Bars
  Demo 6
Exercises

           Physics
Least Squares Fit
  Demo 1
Fit to Polynomial
  Demo 2
Fit Hist Errors
  Demo 3
Discretization
  Demo 4
Timing
  Demo 5
Exercises

  Part I Part II Part III
Java Core 1  2  3  4  5  6  7  8  9  10  11  12 13 14 15 16 17
18 19 20
21
22 23 24
Supplements

1  2  3  4  5  6  7  8  9  10  11  12

Tech 1  2  3  4  5  6  7  8  9  10  11  12
Physics 1  2  3  4  5  6  7  8  9  10  11  12

Java is a trademark of Sun Microsystems, Inc.