Bubble sort animation
Lately I've noticed questions asking about animation of code that uses a looping algorithm. For example:
- Java: How to use swing timer for delaying actions
- How to slow down a for-loop?
The existing code works but only displays the final result. So people want to animate each step of the algorithm. A question is asked because:
- they don't know how to do this, or
- a Thread.sleep(...) has been added to the algorithm, to allow for intermittent painting, but the painting is still only updated once the looping finishes. Of course we know the problem is that you can't use Thread.sleep(...) on the EDT.
In both cases the suggestion was to use a Swing Timer and the question was closed as a duplicate. But is it that easy?
The code below demonstrates a simple Bubble Sort algorithm. The sorting logic is simple and self contained in a single method and indicates where the animation should occur.
import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
import javax.swing.Timer;
public class BubbleSort extends JPanel
{
private final static int BAR_WIDTH = 30;
private final static int BAR_HEIGHT_MAX = 400;
private int[]items;
public BubbleSort(int[] items)
{
this.items = items;
}
public void setItems(int[] items)
{
this.items = items;
repaint();
}
public void sort()
{
int n = items.length;
int temp = 0;
for (int i = 0; i < n; i++)
{
for (int j = 1; j < (n - i); j++)
{
if (items[j-1] > items[j])
{
temp = items[j - 1];
items[j - 1] = items[j];
items[j] = temp;
// paint current state for animation
repaint();
try { Thread.sleep(100); } catch (Exception e) {}
}
}
}
}
@Override
protected void paintComponent(Graphics g)
{
super.paintComponent(g);
for (int i = 0; i < items.length; i++)
{
int x = i * BAR_WIDTH;
int y = getHeight() - items[i];
g.setColor( Color.RED );
g.fillRect(x, y, BAR_WIDTH, items[i]);
g.setColor( Color.BLUE );
g.drawString("" + items[i], x, y);
}
}
@Override
public Dimension getPreferredSize()
{
return new Dimension(items.length * BAR_WIDTH, BAR_HEIGHT_MAX + 20);
}
public static int[]generateRandomNumbers()
{
int[] items = new int[10];
for(int i = 0; i < items.length; i++)
{
items[i] = (int)(Math.random() * BubbleSort.BAR_HEIGHT_MAX);
}
return items;
}
private static void createAndShowGUI()
{
BubbleSort bubbleSort = new BubbleSort( BubbleSort.generateRandomNumbers() );
JButton generate = new JButton("Generate Data");
generate.addActionListener((e) -> bubbleSort.setItems( BubbleSort.generateRandomNumbers() ) );
JButton sort = new JButton("Sort Data");
sort.addActionListener((e) -> bubbleSort.sort());
JPanel bottom = new JPanel();
bottom.add( generate );
bottom.add( sort );
JFrame frame = new JFrame("SSCCE");
frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
frame.add(bubbleSort, BorderLayout.CENTER);
frame.add(bottom, BorderLayout.PAGE_END);
frame.pack();
frame.setLocationByPlatform( true );
frame.setVisible( true );
}
public static void main(String[] args) throws Exception
{
EventQueue.invokeLater( () -> createAndShowGUI() );
}
}
So the questions are:
- How can the code be changed to use a Swing Timer? What tips/pointers do you have?
- Are there other approaches that can be used instead of the Swing Timer?
Another approach might be to use a SwingWorker.
The SwingWorker creates runs in its own Thread and allows you to "publish" intermittent results to be painted.
The key to the approach below is that a copy of the data is passed to the SwingWorker. This allows the worker to sort the data while the data is being repainted so you don't have to worry about the data in the array being in an inconsistent state.
After each iteration of the looping code the new state of the array is updated so it can be painted.
This allows you to easily move the sorting logic into the SwingWorker without refactoring.
import java.awt.*;
import java.awt.event.*;
import java.util.Arrays;
import java.util.List;
import javax.swing.*;
import javax.swing.Timer;
public class BubbleSortWorker extends JPanel
{
private final static int BAR_WIDTH = 30;
private final static int BAR_HEIGHT_MAX = 400;
private int[]items;
public BubbleSortWorker(int[] items)
{
this.items = items;
}
public void setItems(int[] items)
{
this.items = items;
repaint();
}
public void sort()
{
new SortWorker(items).execute();
}
@Override
protected void paintComponent(Graphics g)
{
super.paintComponent(g);
for (int i = 0; i < items.length; i++)
{
int x = i * BAR_WIDTH;
int y = getHeight() - items[i];
g.setColor( Color.RED );
g.fillRect(x, y, BAR_WIDTH, items[i]);
g.setColor( Color.BLUE );
g.drawString("" + items[i], x, y);
}
}
@Override
public Dimension getPreferredSize()
{
return new Dimension(items.length * BAR_WIDTH, BAR_HEIGHT_MAX + 20);
}
class SortWorker extends SwingWorker<Void, int[]>
{
private int[] items;
public SortWorker(int[] unsortedItems)
{
items = Arrays.copyOf(unsortedItems, unsortedItems.length);
}
@Override
protected Void doInBackground()
{
int n = items.length;
int temp = 0;
for (int i = 0; i < n; i++)
{
for (int j = 1; j < (n - i); j++)
{
if (items[j-1] > items[j])
{
temp = items[j - 1];
items[j - 1] = items[j];
items[j] = temp;
//repaint();
publish( Arrays.copyOf(items, items.length) );
try { Thread.sleep(100); } catch (Exception e) {}
}
}
}
return null;
}
@Override
protected void process(List<int[]> list)
{
int[] items = list.get(list.size() - 1);
setItems( items );
}
@Override
protected void done() {}
}
public static int[]generateRandomNumbers()
{
int[] items = new int[10];
for(int i = 0; i < items.length; i++)
{
items[i] = (int)(Math.random() * BubbleSortWorker.BAR_HEIGHT_MAX);
}
return items;
}
private static void createAndShowGUI()
{
BubbleSortWorker bubbleSort = new BubbleSortWorker( BubbleSortWorker.generateRandomNumbers() );
JButton generate = new JButton("Generate Data");
generate.addActionListener((e) -> bubbleSort.setItems( BubbleSortWorker.generateRandomNumbers() ) );
JButton sort = new JButton("Sort Data");
sort.addActionListener((e) -> bubbleSort.sort());
JPanel bottom = new JPanel();
bottom.add( generate );
bottom.add( sort );
JFrame frame = new JFrame("SSCCE");
frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
frame.add(bubbleSort, BorderLayout.CENTER);
frame.add(bottom, BorderLayout.PAGE_END);
frame.pack();
frame.setLocationByPlatform( true );
frame.setVisible( true );
}
public static void main(String[] args) throws Exception
{
EventQueue.invokeLater( () -> createAndShowGUI() );
}
}
Check out Worker Threads and Swing Worker for more information about SwingWorker.