Compare sorting algorithm

Question

I implemented different type of sorting (bubble, insertion, selection). Know I want to compare their implementations like the following for each sort (here's an example with the bubble sort) :

For example, here's my bubble sort :

private static int[] bubbleSort(int[] tabToSort) {
   int [] tab = tabToSort.clone();
   boolean tabSort = false;
   while(!tabSort){
        tabSort = true;
        for(int i = 0; i < tab.length -1; i++){
            if(tab[i]> tab[i+1]){
                int temp = tab[i+1];
                tab[i+1] = tab[i];
                tab[i] = temp;
                tabSort = false;
            }
        }
    }
    return tab;
}

I started the GUI and I placed 1000 random points on it and the line y=x :

@Override
    public void paintComponent (Graphics g){
        super.paintComponent(g);
        Graphics2D g2d  = (Graphics2D) g;
        g2d.setColor(Color.BLACK);
        Dimension size = getSize();
        Insets  insets= getInsets();
        int w =  size.width - insets.left - insets.right;
        int h =  size.height - insets.top - insets.bottom;
        
        g2d.drawLine(size.width ,0, 0, size.height);
        Random r = new Random();

        for (int i  =0; i < 1000; i++) {
           int x = Math.abs(r.nextInt()) % w;
           int y = Math.abs(r.nextInt()) % h;
           Point p = new Point(x, y);
           g2d.drawLine(p.x, p.y, p.x, p.y);
        }
    }

Here's what I've done :

Now I'm stuck, I have no idea about how to start. Could anyone indicate me the steps/ hints to follow to implement that ?

Thanks :)

Answer 1

You must define what the points mean. Looking at the animation, it looks like the y axis represents a value, whilst the x axis represents the position in the array of that value.

In your paint method, you would then go through the list of items and paint a dot, with the x-point being the position in the array and the y-point being a position on the y-axis. Assuming the values are within a known range.

Also, remember that the y-axis in graphics starts with 0 at the top, so you may have to do some translation of values to coordinates (depending on how you want it to look).

Answer 2

The easiest way would be to convert your paint method into one that uses a predefined List of points as a parameter instead of random points. On each iteration of your sort method pass the sorted array into the paint method and repaint the dots.

Answer 3

You'll need to

1. Create an int[] array with random values as a member variable. Let's call the array data. You probably want to start with a fixed array size and range of 100 each. You can adjust the values to the window size later, when a simple version is working. It may be even better to stick to a fixed size and range and just scale to the space available in paintComponent, making the behavior independent of the window size.
2. Change paintComponent to loop over data. The loop index is your x value and data[x] determines the y value.
3. Test that the code still draws the initial random array. Don't care if it is in the uppler left corner only now, you can fix that when the animation is working.
4. You'll need to add some kind of sleep() call to the innermost loop of your sort method, so you get a chance to observe the steps. Otherwise, even bubblesort will be too fast to observe. I'd recommend to start with one second (parameter value 1000). Make it faster later when everything works.
5. Start the bubbleSort method in a new thread and make sure your component gets repainted with each step. This may be the most tricky part. Perhaps hand in the component to the bublleSort method (or make bubbleSort a non-static method of the component) and let it request a repaint() at each step (fortunately, this is one of the few thread safe methods in Swing).
6. Fine-tune your code: Scale the x and y coordinates by multiplying with the space available and then dividing by the array size or value range. Adjust the sleep time as needed. Add support for different sorting algorithms....

If any of the steps is unclear, add a comment.

Answer 4

I've done this for my bachelorthesis, I did it like this (it's not perfect, but it might help you):

(I removed some unimportant methods/functions from the code below. It's mainly to illustrate how I visualized it. You can replace the GRectangle class by a simple java.awt.Point for example.)

The initialization method gives you an example of how you can find the maximum and minimum value of the data so you know how to transform your datavalues => coordinates.

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

Take this into account: Visualizing integers between 0 and 150 on a height of 150 pixels is straightforward. Visualizing a set of integers between the values 565 and 3544545 on a height of 150 is a bit less so.

PS: The code uses the index of the element in the inputarray as the X-coordinate.
PS: The class keeps a reference to the inputarray (m_data variable) but that's ofcourse not needed, you only need it to initialize your points.
PS: My "Visualization" class which is extended by all visualizations, is basicly a JPanel.
PS: The code above is written for positive integers, so will probably need some extra coding to handle negative integers aswell ;).

Then to visualize the actions of the algorithm, I used the observer pattern. The algorithm, for example bubblesort, looked like this:

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

Where the function swap was defined as follows (simplified version again):

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

Where I notified my observers (visualizations) that a swap occured on index1 and index2. The m_command variable is an instance of the Command-class (wrote it myself) which is just a wrapper for the information needed by the visualization. Which is: the action that occured and the relevant information (indices for a swap-action for example).

So in the visualization i swapped the GRectangles on those indices aswell as their X-coordinates;

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

You can add lines like this:

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

to let a thread sleep 100ms before continueing. This might come in handy if it's getting visualized too fast.

So for an array with random integers it might look like this:

And after sorting: (Ofcourse it's not a straight line because the values in the inputarray were generated at random in this case)

So if you have to - like I had to - allow multiple algorithms to work with the same visualization, I can recommend you to separate the visualization class and the algorithm class and work with an observer pattern to let the visualization update whenever an action occurs (set, swap, ...).

And then you can create something like this for comparisons;

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

Good luck!