Compare Sort Algorithm

Question

I implemented a different type of sorting (bubble, insert, select). I know that I want to compare their implementations as the following for each view (here is an example with bubble sorting):

For example, here is 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 dots 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(px, py, px, py); } } 

Here is what I did:

Now I'm stuck, I have no idea how to start. Can someone point me to the steps / tips to follow this to implement this?

Thanks:)

Answer 1

You must determine what the dots mean. Looking at the animation, it looks like this: the y axis represents value , and the x axis represents position in the array of this value.

In your paint method, you will go through a list of elements and draw a point where the x-point will be the position in the array and the y-point will be the position along the y axis. Assuming the values ​​are within a known range.

Also, remember that the y axis in the graph starts at 0 from the top, so you may need to translate the values ​​into coordinates (depending on how you want it to look).

Answer 2

The easiest way is to convert your drawing method to one that uses predefined List points as a parameter instead of random points. At each iteration of your sorting method, pass the sorted array to the drawing method and redraw the points.

Answer 3

You need

• Create an int[] array with random values ​​as a member variable. Let us call the data array. You probably want to start with a fixed array size and a range of 100 pieces. You can adjust the values ​​to the window size later when the simple version is running. It might even be better to stick with a fixed size and range and just scale to the place available in paintComponent , making the behavior independent of window size.
• Change paintComponent to data loop. The loop index is your x value, and data[x] defines the y value.
• Verify that the code is still drawing the original random array. I do not care, only now it is in the left corner of the uppler, you can fix it when the animation works.
• You need to add some sort of sleep() call to the innermost loop of your sort method so that you can watch the steps. Otherwise, even the bubble system will be too fast to observe. I would recommend starting with one second (parameter value 1000). Make it faster when everything works.
• Run the bubbleSort method in a new thread and make sure your component is redrawn with each step. This may be the hardest part. Perhaps pass the component to the bublleSort method (or make the bubbleSort non-static component method) and let it request repaint() at each step (fortunately, this is one of the few methods protected by threads in Swing).
• Fine-tuning your code: scale the x and y coordinates by multiplying them by free space and dividing by the size of the array or range of values. Adjust your sleep time if necessary. Add support for different sorting algorithms ....

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

Answer 4

I did it for my bachelor, I did it like this (this is not perfect, but it could help you):

(I removed some irrelevant methods / functions from the code below. Basically, to illustrate how I rendered it. You can replace the GRectangle class with 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 that you know how to convert the data datavalues ​​=>.

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

Keep this in mind: Rendering integers from 0 to 150 at a height of 150 pixels is simple. Rendering a set of integers between the values ​​565 and 3544545 at a height of 150 is slightly smaller.

PS: the code uses the element index in inputarray as the X coordinate.
PS: the class stores a reference to the variable inputarray (variable m_data), but, of course, it is not needed, you only need to initialize it with your glasses.
PS: My Visualization class, which expands with all visualizations, is basically JPanel.
PS: the above code is written for positive integers, so you probably need extra coding to handle negative integers;).

Then, to visualize the actions of the algorithm, I used the observer pattern. An algorithm, such as 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); 

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

 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 (visualization) that the swap occurred on index1 and index2. The m_command variable is an instance of the Command class (he wrote it), which is just a wrapper for the information needed for visualization. Which: the action that occurred, and related information (for example, indexes for the swap action).

Thus, during visualization, I changed GRectangles to these indices, as well 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 these lines:

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

so that the thread overslept 100 ms before continuing. This can come in handy if you render it too quickly.

So, for an array with random integer values, it might look like this:

And after sorting: (Of course, this is not a straight line, because in this case the values ​​in the input symbol were randomly generated)

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

And then you can create something similar for comparison;

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

Good luck