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
|