Сравнить алгоритм сортировки

Самый простой способ-преобразовать метод paint в метод, который использует в качестве параметра заранее заданное List количество точек вместо случайных точек. На каждой итерации метода сортировки передайте отсортированный массив в метод paint и перекрасьте точки.

Вам нужно будет

1. создайте массив int[] со случайными значениями в качестве переменной-члена. Назовем массив data. Вы, вероятно, хотите начать с фиксированного размера массива и диапазона 100 каждый. Вы можете настроить значения по размеру окна позже, когда простая версия будет работать. Возможно, даже лучше придерживаться фиксированного размера и диапазона и просто масштабировать пространство, доступное в paintComponent, делая поведение независимым от размера окна.
2. измените paintComponent на цикл data. Индекс цикла - это ваше значение x, а data[x] определяет значение Y.
3. проверьте, что код все еще рисует начальный случайный массив. Не волнуйтесь, если он находится в верхнем левом углу только сейчас, вы можете исправить это, когда анимация работает.
4. вам нужно будет добавить какой-то вызов sleep() к самому внутреннему циклу вашего метода сортировки, чтобы вы могли наблюдать шаги. В противном случае даже пузырчатка будет слишком быстрой для наблюдения. Я бы рекомендовал начать с одной секунды (значение параметра 1000). Сделайте это быстрее позже, когда все будет работать.
5. запустите метод bubbleSort в новом потоке и убедитесь, что ваш компонент перерисовывается с каждым шагом. Это может быть самая сложная часть. Возможно, передать компонент методу bublleSort (или сделать bubbleSort нестатическим методом компонента) и позволить ему запрашивать repaint() на каждом шаге (к счастью, это один из немногих потокобезопасных методов в Swing).
6. точная настройка кода: масштабирование координат x и y путем умножения на пространство доступно и затем делится на размер массива или диапазон значений. Отрегулируйте время сна по мере необходимости. Добавьте поддержку различных алгоритмов сортировки....

Если какой-либо из шагов неясен, добавьте комментарий.

Я сделал это для моей холостяцкой диссертации, я сделал это так (это не идеально, но это может помочь вам):

(я удалил некоторые неважные методы / функции из кода ниже. В основном, чтобы проиллюстрировать, как я это себе представлял. Вы можете заменить класс GRectangle простым java.ОУ.Например, точка.)

Метод инициализации дает вам пример того, как вы можете найти максимальное и минимальное значение данных, чтобы вы знали, как преобразовать ваши значения данных => координирует.

public class DotVisualisation extends Visualisation {

    private ArrayList<GRectangle> m_points;

    private Comparable[] m_data;

    private Comparable m_maxValue;
    private Comparable m_minValue;

    private int MAX_HEIGHT; // max height in pixels of visualization

    /**
     * Creates a new DotVisualisation.<br>
     * <br>
     * This class is a runnable JComponent that will visualize data as a function. 
     * The visualisation will plot the data with X and Y coordinates on the window. 
     * The X coordinate of the point is index of the dataelement. 
     * The Y coordinate of the point is relative to the value of the dataelement.<br>
     * <br>
     * This visualisation should be used for medium and large arrays.
     * 
     * @author David Nysten
     */
    public DotVisualisation()
    {
        m_points = new ArrayList<GRectangle>();
        MAX_HEIGHT = 150;
    }

    /**
     * Returns the maximum supported dimension by this visualisation.
     * 
     * @return The supported dimension.
     */
    public static int getSupportedDimension()
    {
        return 1;
    }

    @Override
    public Dimension getMaximumSize() 
    {
        return getPreferredSize();
    }

    @Override
    public Dimension getPreferredSize() 
    {
        return new Dimension(m_points.size() + 2, MAX_HEIGHT + 6);
    }

    @Override
    public Dimension getMinimumSize() 
    {
        return getPreferredSize();
    }

    @Override
    public void paintComponent(Graphics g)
    {
        for(int i = 0; i < m_points.size(); ++i)
            m_points.get(i).paintComponent(g);
    }

    private void swap(int index, int index2) { // See below }

    private void initialise()
    {
        findMinimum();
        findMaximum();
        m_points.clear();
        double multiplier;
        int x = 0, y = 0, h;
        for(int i = 0; i < m_data.length; ++i)
        {
            if(m_data[i].compareTo(-1) <= 0)
                h = 0;
            else
            {
                Integer value = (Integer) m_data[i];
                Integer min = (Integer) m_minValue;
                Integer diff = (Integer) m_maxValue - min;
                multiplier = MAX_HEIGHT / diff.doubleValue();
                h = (int) ((value - min) * multiplier);
            }
            y = (int) (MAX_HEIGHT - h);
            GRectangle r = new GRectangle(x, y, 1, 1); // 1, 1 = width and height
            r.setColor(Color.BLACK);
            m_points.add(r);
            ++x;
        }
    }

    private void findMaximum()
    {
        Comparable max = null;
        if(m_data.length > 0)
        {
            max = m_data[0];
            for(int i = 1; i < m_data.length; ++i)
                if(m_data[i].compareTo(max) > 0)
                    max = m_data[i];
        }
        m_maxValue = max;
    }

    private void findMinimum()
    {
        Comparable min = null;
        if(m_data.length > 0)
        {
            min = m_data[0];
            for(int i = 1; i < m_data.length; ++i)
                if(m_data[i].compareTo(min) < 0)
                    min = m_data[i];
        }
        m_minValue = min;
    }
}

Примите это во внимание: Визуализация целых чисел от 0 до 150 на высоте 150 пикселей проста. Визуализация набора целых чисел между значениями 565 и 3544545 на высоте 150 немного меньше.

PS: код использует индекс элемента inputarray в качестве координаты X.
PS: класс сохраняет ссылку на inputarray (переменную m_data), но это, конечно, не нужно, вам нужно только инициализировать ваши точки.
PS: мой Класс "визуализация", который расширяется всеми визуализациями, в основном является JPanel.
PS: приведенный выше код написан для положительных целых чисел, поэтому, вероятно, потребуется дополнительное кодирование для обработки отрицательных целых чисел;).

Затем, чтобы визуализировать действия алгоритма, я использовал шаблон наблюдателя. Алгоритм, например bubblesort, выглядел так:

    for(int i = 0; i < size(); ++i)
        for(int j = 1; j < size(); ++j)
            if(greaterThan(j - 1, j))
                swap(j - 1, j);

Где функция swap была определена следующим образом (опять упрощенная версия):

protected void swap(int index1, int index2)
{
    if(index1 != index2)
    {
        incrementSwap(); // counting swaps and visualizing counter

        m_command.clear();
        m_command.setAction(Action.SWAP);
        m_command.addParameter(index1);
        m_command.addParameter(index2);
        setChanged();
        notifyObservers(m_command);

        E temp = m_data[index1];
        m_data[index1] = m_data[index2];
        m_data[index2] = temp;
    }
}

Где Я уведомил моих наблюдателей (визуализаций), что своп произошел на индексах index1 и index2. Переменная m_command-это экземпляр класса Command (я сам ее написал), который является всего лишь оболочкой для информации, необходимой визуализации. То есть: действие, которое произошло, и соответствующая информация (индексы для своп-действия, например).

Таким образом, в визуализации я поменял местами греческие треугольники на эти индексы, а также их координаты X;

private void swap(int index, int index2)
{
    if(index == index2)
        return;
    GRectangle r1 = m_points.get(index);
    GRectangle r2 = m_points.get(index2);

    int tempX = r1.getX();
    r1.setLocation(r2.getX(), r1.getY());
    r2.setLocation(tempX, r2.getY());

    m_points.set(index, r2);
    m_points.set(index2, r1);
}

Вы можете добавить такие строки, как это:

        try {
            Thread.sleep(100);
        } catch(InterruptedException ignore) {}

Чтобы поток спал 100 мс перед продолжением. Это может пригодиться, если он визуализируется слишком быстро.

Таким образом, для массива со случайными целыми числами это может выглядеть следующим образом:

И после сортировки: (Конечно, это не прямая линия, потому что значения в inputarray были сгенерированы случайным образом в этом случае)

Поэтому, если вам нужно - как и мне-разрешить нескольким алгоритмам работать с одной и той же визуализацией, я можно рекомендовать разделить класс визуализации и класс алгоритма и работать с шаблоном наблюдателя, чтобы визуализация обновлялась всякий раз, когда происходит действие (set, swap,...).

И тогда вы можете создать что-то вроде этого для сравнения;

Http://i445.photobucket.com/albums/qq179/ultddave/DotVisualizationMany_zps63269d2a.png http://i445.photobucket.com/albums/qq179/ultddave/DotVisualizationMany2_zps65e96fa9.png

Удачи!