Bubble sort animation

Question

Lately I've noticed questions asking about animation of code that uses a looping algorithm. For example:

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?

camickr · Accepted Answer · 2022-02-26T16:21:48.170

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;
    private boolean everySwap;

    public BubbleSortWorker(int[] items, boolean everySwap)
    {
        this.items = items;
        this.everySwap = everySwap;
    }

    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;

                        //  Update after every swap is done

                        if (everySwap)
                        {
                            publish( Arrays.copyOf(items, items.length) );
                            try { Thread.sleep(100); } catch (Exception e) {}
                        }
                    }
                }

                //  Update once per iteration

                if (!everySwap)
                {
                    publish( Arrays.copyOf(items, items.length) );
                    try { Thread.sleep(500); } 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(), true);

        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.

camickr · Answer 2 · 2022-02-26T15:24:06.037

A Swing Timer works on event driven code. Therefore the iterative code must be refactored to event driven code.

Some things to consider during this process:

state must be added to the algorithm. This means that all local variables used to control the looping algorithm must be converted to instance variables of the class.
the looping algorithm must be split into two methods, the first to set the initial state of the algorithm and start the timer, and the second method to update the state and stop the Timer.

Using the above suggestion the refactoring of your code might be something like:

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

public class BubbleSortTimer extends JPanel
{
    private final static int BAR_WIDTH = 30;
    private final static int BAR_HEIGHT_MAX = 400;

    private int[]items;
    private int i, j, n;
    private Timer timer;

    public BubbleSortTimer(int[] items)
    {
        this.items = items;

        timer = new Timer(100, (e) ->
        {
            if (!nextIteration())
            {
                timer.stop();
            }

            repaint();
        });
    }

    public void setItems(int[] items)
    {
        this.items = items;
        repaint();
    }

    public void sort()
    {
        i = 0;
        j = 1;
        n = items.length;

        timer.start();
    }

    public boolean nextIteration()
    {
        if (items[j - 1] > items[j])
        {
            int temp = items[j - 1];
            items[j - 1] = items[j];
            items[j] = temp;
        }

        j++;

        if (j >= n - i)
        {
            j = 1;
            i++;
        }

        return i != n;
    }

    @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() * BubbleSortTimer.BAR_HEIGHT_MAX);
        }

        return items;
    }

    private static void createAndShowGUI()
    {
        BubbleSortTimer bubbleSort = new BubbleSortTimer( BubbleSortTimer.generateRandomNumbers() );

        JButton generate = new JButton("Generate Data");
        generate.addActionListener((e) -> bubbleSort.setItems( BubbleSortTimer.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() );
    }
}

Bubble sort animation

2 Answers2

Linked