Bubble-Sort-Animation

Question

In letzter Zeit sind mir Fragen zur Animation von Code aufgefallen, der einen Schleifenalgorithmus verwendet. Zum Beispiel:

1. Java: Verwendung des Swing-Timers zum Verzögern von Aktionen
2. Wie verlangsame ich eine for-Schleife?

Der vorhandene Code funktioniert, zeigt jedoch nur das Endergebnis an. Die Leute wollen also jeden Schritt des Algorithmus animieren. Eine Frage wird gestellt, weil:

1. sie wissen nicht, wie sie das machen sollen, oder
2. Dem Algorithmus wurde ein Thread.sleep (...) hinzugefügt, um ein intermittierendes Malen zu ermöglichen. Das Malen wird jedoch erst nach Abschluss der Schleife aktualisiert. Natürlich wissen wir, dass das Problem darin besteht, dass Sie Thread.sleep (...) nicht auf dem EDT verwenden können.

In beiden Fällen wurde vorgeschlagen, einen Swing-Timer zu verwenden, und die Frage wurde als Duplikat geschlossen. Aber ist es so einfach?

Der folgende Code zeigt einen einfachen Bubble-Sort-Algorithmus. Die Sortierlogik ist einfach und in einer einzigen Methode enthalten und gibt an, wo die Animation stattfinden soll.

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() );
    }
}

Die Fragen sind also:

1. Wie kann der Code geändert werden, um einen Swing-Timer zu verwenden? Welche Tipps / Hinweise haben Sie?
2. Gibt es andere Ansätze, die anstelle des Swing-Timers verwendet werden können?

Answer 1

Ein anderer Ansatz könnte darin bestehen, einen SwingWorker zu verwenden.

Der SwingWorker erstellt Läufe in einem eigenen Thread und ermöglicht es Ihnen, intermittierende Ergebnisse zu "veröffentlichen", die gezeichnet werden sollen.

Der Schlüssel zum folgenden Ansatz besteht darin, dass eine Kopie der Daten an SwingWorker übergeben wird. Auf diese Weise kann der Worker die Daten sortieren, während die Daten neu gestrichen werden, sodass Sie sich keine Sorgen machen müssen, dass sich die Daten im Array in einem inkonsistenten Zustand befinden.

Nach jeder Iteration des Schleifencodes wird der neue Status des Arrays aktualisiert, damit es gezeichnet werden kann.

Auf diese Weise können Sie die Sortierlogik ohne Refactoring einfach in den SwingWorker verschieben.

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() );
    }
}

Answer 2

Ein Swing-Timer arbeitet mit ereignisgesteuertem Code. Daher muss der iterative Code in ereignisgesteuerten Code umgestaltet werden.

Einige Dinge, die während dieses Prozesses zu beachten sind:

1. Der Status muss dem Algorithmus hinzugefügt werden. Dies bedeutet, dass alle lokalen Variablen, die zur Steuerung des Schleifenalgorithmus verwendet werden, in Instanzvariablen der Klasse konvertiert werden müssen.

2. Der Schleifenalgorithmus muss in zwei Methoden aufgeteilt werden, die erste, um den Anfangszustand des Algorithmus festzulegen und den Timer zu starten, und die zweite Methode, um den Zustand zu aktualisieren und den Timer zu stoppen.

Mit dem obigen Vorschlag könnte das Refactoring Ihres Codes ungefähr so ​​aussehen:

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) -> nextIteration());
    }

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

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

        timer.start();
    }

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

            repaint();
        }

        j++;

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

        if (i == n)
            timer.stop();
    }

    @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() );
    }
}