1 import java.awt.Color;
2 import java.awt.Graphics;
3 import java.util.concurrent.locks.Lock;
4 import java.util.concurrent.locks.ReentrantLock;
5 import javax.swing.JComponent;
6
7 /**
8 This class sorts an array, using the selection sort algorithm.
9 */
10 public class SelectionSorter
11 {
12 // This array is being sorted
13 private int[] a;
14 // These instance variables are needed for drawing
15 private int markedPosition = -1;
16 private int alreadySorted = -1;
17
18 private Lock sortStateLock;
19
20 // The component is repainted when the animation is paused
21 private JComponent component;
22
23 private static final int DELAY = 100;
24
25 /**
26 Constructs a selection sorter.
27 @param anArray the array to sort
28 @param aComponent the component to be repainted when the animation
29 pauses
30 */
31 public SelectionSorter(int[] anArray, JComponent aComponent)
32 {
33 a = anArray;
34 sortStateLock = new ReentrantLock();
35 component = aComponent;
36 }
37
38 /**
39 Sorts the array managed by this selection sorter.
40 */
41 public void sort()
42 throws InterruptedException
43 {
44 for (int i = 0; i < a.length - 1; i++)
45 {
46 int minPos = minimumPosition(i);
47 sortStateLock.lock();
48 try
49 {
50 ArrayUtil.swap(a, minPos, i);
51 // For animation
52 alreadySorted = i;
53 }
54 finally
55 {
56 sortStateLock.unlock();
57 }
58 pause(2);
59 }
60 }
61
62 /**
63 Finds the smallest element in a tail range of the array
64 @param from the first position in a to compare
65 @return the position of the smallest element in the
66 range a[from]...a[a.length - 1]
67 */
68 private int minimumPosition(int from)
69 throws InterruptedException
70 {
71 int minPos = from;
72 for (int i = from + 1; i < a.length; i++)
73 {
74 sortStateLock.lock();
75 try
76 {
77 if (a[i] < a[minPos]) { minPos = i; }
78 // For animation
79 markedPosition = i;
80 }
81 finally
82 {
83 sortStateLock.unlock();
84 }
85 pause(2);
86 }
87 return minPos;
88 }
89
90 /**
91 Draws the current state of the sorting algorithm.
92 @param g the graphics context
93 */
94 public void draw(Graphics g)
95 {
96 sortStateLock.lock();
97 try
98 {
99 int deltaX = component.getWidth() / a.length;
100 for (int i = 0; i < a.length; i++)
101 {
102 if (i == markedPosition)
103 {
104 g.setColor(Color.RED);
105 }
106 else if (i <= alreadySorted)
107 {
108 g.setColor(Color.BLUE);
109 }
110 else
111 {
112 g.setColor(Color.BLACK);
113 }
114 g.drawLine(i * deltaX, 0, i * deltaX, a[i]);
115 }
116 }
117 finally
118 {
119 sortStateLock.unlock();
120 }
121 }
122
123 /**
124 Pauses the animation.
125 @param steps the number of steps to pause
126 */
127 public void pause(int steps)
128 throws InterruptedException
129 {
130 component.repaint();
131 Thread.sleep(steps * DELAY);
132 }
133 }