kamils40
kamils40

Reputation: 27

QuickSort visualisation via java swing

I wanted to make some kind of sorting algorithms visualisation is java swing but I am stuck on quicksort since I need to stop the partition loop every iteration so the array can redraw. That's how I wanted to do it but without any success

 public int partition(int lowIndex, int highIndex,int i)
    {
        int pivot = highIndex;

        for(int j=lowIndex; j<highIndex; j++)
        {
            if(isBigger(j,pivot))
            {
                i++;
                swap(i,j);
                return i;
            }
        }
         swap(i+1,pivot);

        return i+1;
    }

Didn't find any good solution to keep track on i as well. I'm just clueless

Upvotes: 0

Views: 494

Answers (2)

kamils40
kamils40

Reputation: 27

Instead of calling partition from other class I implemented partition() and sort() methods in an anonymous SwingWorker class and after every swap in partition() method I called publish(array). Uploading source code if anyone would like to see how I solved this problem or would need help himself. Any feedback is really appreciate since it's my first "bigger" project

 private  void startThread()
    {
            SwingWorker sw1 = new SwingWorker()  {
                public int partition(int lowIndex, int highIndex) {
                    int pivot = highIndex;
                    int i = lowIndex - 1;
                    for (int j = lowIndex; j < highIndex; j++) {
                        if (sorter.isBigger(pivot, j)) {

                            i++;
                            sorter.swap(i, j);
                            try {
                                Thread.sleep(100);
                            }
                            catch(Exception e)
                            {
                                // not implemented yet
                            }
                            publish(sorter.getArray());
                        }

                    }
                    sorter.swap(i+1,pivot);
                    publish(sorter.getArray());
                    return i+1;
                }
                public void sort(int lowIndex, int highIndex)
                {

                    if(lowIndex < highIndex)
                    {
                        int i = partition(lowIndex,highIndex);
                        try{
                           sort(lowIndex,i-1) ;
                        }
                        finally {
                            sort(i+1, highIndex);
                        }

                    }
                }
                @Override
                protected int[] doInBackground() throws Exception {
                    sorter.setArray(drafter.getArray());
                    while (!sorter.isArraySorted()) {
                        //Thread.sleep(10);
                        sort(0,sorter.getLength()-1);

                        }


                    return sorter.getArray();
                }
                protected void process(List chunks)
                {
                    int[] val = (int[]) chunks.get(chunks.size()-1);
                    drafter.ChangeArray(val);
                    //drafter.repaint();

                }

                };
            sw1.execute();

    }

Upvotes: 1

paulsm4
paulsm4

Reputation: 121881

Google for "Java swing visualize sorting algorithms" and you'll find many hits.

For example:

Code Review: sorting algorithm visualization program

Key points:

  • You need to modify your "sort" code to trigger some kind of "event" at each step (e.g. every time you swap elements):

    EXAMPLE:

    public class BubbleSort implements SortingAlgorithm {
      ...
      @Override
      public void doSort(int[] nums) {
        ...
        SortingAlgorithm.setCurrentBar(j+1);
        SortingAlgorithm.sleepFor(delay);
    
  • The "event handler" will redraw the array (or, more accurately, request the Event Dispatcher thread (EDT) to repaint).

  • Consequently, the event handler needs to "know about" the array, and the current index

    EXAMPLE:

    public abstract interface SortingAlgorithm {
      ...
      public abstract void doSort(int[] nums);
    
      public abstract void changeDelay(int delay);
    
      public static void setCurrentBar(int currentBarIndex) {
        PaintSurface.currentBarIndex = currentBarIndex;
      }
      ...
    
  • There also needs to be some kind of "delay" between each step

  • This example uses SwingUtilities.invokeLater(). The example camickr suggests SwingWorker.

I hope that gives you a few ideas, and points you in the right direction!

Upvotes: 1

Related Questions