001: import java.applet.Applet;
002: import java.awt.Color;
003: import java.awt.Graphics2D;
004: import java.awt.geom.Line2D;
005: 
006: /**
007:    This class sorts an array, using the selection sort 
008:    algorithm
009: */
010: public class SelectionSorter
011: {
012:    /**
013:       Constructs a selection sorter.
014:       @param anArray the array to sort.
015:    */
016:    public SelectionSorter(int[] anArray, Applet anApplet)
017:    {
018:       a = anArray;
019:       applet = anApplet;
020:    }
021: 
022:    /**
023:       Sorts the array managed by this selection sorter.
024:    */
025:    public void sort() 
026:       throws InterruptedException
027:    {  
028:       for (int i = 0; i < a.length - 1; i++)
029:       {  
030:          int minPos = minimumPosition(i);
031:          swap(minPos, i);
032:          // for animation
033:          alreadySorted = i;
034:          pause(2);
035:       }
036:    }
037: 
038:    /**
039:       Finds the smallest element in a tail range of the array
040:       @param from the first position in a to compare
041:       @return the position of the smallest element in the
042:       range a[from]...a[a.length - 1]
043:    */
044:    private int minimumPosition(int from)
045:       throws InterruptedException
046:    {  
047:       int minPos = from;
048:       for (int i = from + 1; i < a.length; i++)
049:       {
050:          if (a[i] < a[minPos]) minPos = i;
051:          // for animation
052:          markedPosition = i;
053:          pause(2);
054:       }
055:       return minPos;
056:    }
057: 
058:    /**
059:       Swaps two entries of the array.
060:       @param i the first position to swap
061:       @param j the second position to swap
062:    */
063:    private void swap(int i, int j)
064:    {
065:       int temp = a[i];
066:       a[i] = a[j];
067:       a[j] = temp;
068:    }
069: 
070:    /**
071:       Draws the current state of the sorting algorithm.
072:       @param g2 the graphics context
073:    */
074:    public void draw(Graphics2D g2)
075:    {
076:       int deltaX = applet.getWidth() / a.length;
077:       for (int i = 0; i < a.length; i++)
078:       {
079:          if (i == markedPosition)
080:             g2.setColor(Color.red);
081:          else if (i <= alreadySorted)
082:             g2.setColor(Color.blue);
083:          else
084:             g2.setColor(Color.black);
085:          g2.draw(new Line2D.Double(i * deltaX, 0, 
086:             i * deltaX, a[i]));
087:       }
088:    }
089: 
090:    /**
091:       Pauses the animation.
092:       @param steps the number of steps to pause
093:    */
094:    public void pause(int steps) 
095:       throws InterruptedException
096:    {
097:       if (Thread.currentThread().isInterrupted()) 
098:          throw new InterruptedException();
099:       applet.repaint();
100:       Thread.sleep(steps * DELAY);
101:    }
102: 
103:    private int[] a;
104: 
105:    // the applet is needed for pausing the animation
106:    private Applet applet;   
107:    
108:    // these fields are needed for drawing 
109:    private int markedPosition = -1;
110:    private int alreadySorted = -1;
111: 
112:    private static final int DELAY = 100;
113: }