Animasi bubble sort

Question

Akhir-akhir ini saya memperhatikan pertanyaan yang menanyakan tentang animasi kode yang menggunakan algoritma perulangan. Sebagai contoh:

1. Java: Cara menggunakan pengatur waktu ayunan untuk menunda tindakan
2. Bagaimana cara memperlambat for-loop?

Kode yang ada berfungsi tetapi hanya menampilkan hasil akhir. Jadi orang ingin menganimasikan setiap langkah algoritme. Sebuah pertanyaan ditanyakan karena:

1. mereka tidak tahu bagaimana melakukan ini, atau
2. sebuah Thread.sleep (...) telah ditambahkan ke algoritme, untuk memungkinkan pengecatan intermiten, tetapi pengecatan masih hanya diperbarui setelah perulangan selesai. Tentu saja kami tahu masalahnya adalah Anda tidak dapat menggunakan Thread.sleep (...) di EDT.

Dalam kedua kasus, sarannya adalah menggunakan Pengatur Waktu Ayun dan pertanyaan ditutup sebagai duplikat. Tapi apakah semudah itu?

Kode di bawah ini menunjukkan algoritme Bubble Sort sederhana. Logika pengurutan sederhana dan mandiri dalam satu metode dan menunjukkan tempat animasi harus terjadi.

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

Jadi pertanyaannya adalah:

1. Bagaimana kode diubah untuk menggunakan Pengatur Waktu Ayun? Tips / petunjuk apa yang Anda miliki?
2. Apakah ada pendekatan lain yang dapat digunakan selain Pengatur Waktu Ayun?

Answer 1

Pendekatan lain mungkin menggunakan SwingWorker.

SwingWorker membuat proses di Thread-nya sendiri dan memungkinkan Anda untuk "mempublikasikan" hasil berselang untuk dicat.

Kunci pendekatan di bawah ini adalah bahwa salinan data diteruskan ke SwingWorker. Ini memungkinkan pekerja untuk mengurutkan data saat data sedang dicat ulang sehingga Anda tidak perlu khawatir data dalam larik berada dalam keadaan yang tidak konsisten.

Setelah setiap iterasi kode perulangan, status baru dari larik diperbarui sehingga dapat dicat.

Ini memungkinkan Anda dengan mudah memindahkan logika pengurutan ke SwingWorker tanpa pemfaktoran ulang.

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

Timer Ayun bekerja pada kode yang digerakkan oleh peristiwa. Oleh karena itu, kode iteratif harus direfraktorisasi menjadi kode yang digerakkan oleh peristiwa.

Beberapa hal yang perlu diperhatikan selama proses ini:

1. negara bagian harus ditambahkan ke algoritme. Ini berarti bahwa semua variabel lokal yang digunakan untuk mengontrol algoritme perulangan harus diubah menjadi variabel instance kelas.

2. algoritma perulangan harus dipecah menjadi dua metode, yang pertama untuk mengatur status awal dari algoritma dan memulai pengatur waktu, dan metode kedua untuk memperbarui keadaan dan menghentikan Pengatur waktu.

Menggunakan saran di atas, pemfaktoran ulang kode Anda mungkin seperti ini:

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