Help on the Efficiency of Bubble Sort Visualization

TheApexTheater

I recently programmed a visualization of the bubble sorting algorithm that, while works, takes a significant chunk of time and energy to run. My question is... Is there a better way to do this?

Side note, a feature I'm interested in implementing is that, whenever a swap is made, the program makes a sound (I included the library in the code)

 import processing.sound.*;
SinOsc sine;

int numOfEntries = 200;
int rectWidth;
int randomUnsortedArray[] ;
void setup()
{
  size(1000, 1000);
  background(255);
  randomUnsortedArray = new int[numOfEntries];

  rectMode(CORNERS);
  for (int i = 0; i < numOfEntries; i++)
  { //Gives each element in the array a random value
    randomUnsortedArray[i] = int(random(height));
  }
}

void draw()
{
  frameRate(120);
  randomUnsortedArray = bubbleSort(randomUnsortedArray);

  for (int i = 0; i < numOfEntries; i++)
  {
    fill(255);
    rect(i*rectWidth, height, rectWidth*(i+1), height-randomUnsortedArray[i]);
  }
}

int numOfComparisons =0;
int [] bubbleSort(int unsortedArray[])
{
  background(0);
  float rectWidth = width/unsortedArray.length;
  boolean swap;
  for (int h = 0; h < numOfEntries; h++)
  { //Redraws entire array of rectangles
    fill(255);
    rect(h*rectWidth, height, rectWidth*(h+1), height-randomUnsortedArray[h]);
  }
  swap=false;
  for (int i = 0; i < unsortedArray.length - 1; i++)
  {
    if (unsortedArray[i] > unsortedArray[i+1])
    {
      fill(90, 132, 78);
      rect(rectWidth*(i+1), height, rectWidth*(i+2), height-unsortedArray[i+1]);
      sine = new SinOsc(this);
      sine.play(); //Program eventually crashes
      //begin swap
      int temp = unsortedArray[i];
      unsortedArray[i] = unsortedArray[i+1];
      unsortedArray[i+1]= temp;
      swap = true;
      //end swap

      numOfComparisons++;
      print("Number of Comparisons: " +numOfComparisons + "\n");
      break;
    }
  }
  return unsortedArray;
}

GoToLoop

http://docs.Oracle.com/javase/8/docs/api/java/util/Arrays.html#sort-T:A-java.util.Comparator-
http://docs.Oracle.com/javase/8/docs/api/java/util/Comparator.html

quark

Unfortunately The bubble sort algorithm is incorrectly implemented.

TheApexTheater

@quark... How so? The sort essentially does the following: If one value is larger than the next value, swap them, and it works as intended.

@GoToLoop, I appreciate the links to the Java documentation, but I'm having a difficult time seeing how the Comparator interface would help me implement a visualization

GoToLoop

https://forum.Processing.org/two/discussions/tagged/comparator

https://forum.Processing.org/two/discussion/8973/sorting-list-of-objects-by-object-variable#Item_3

quark

If one value is larger than the next value, swap them,

Yes but then it stops (breaks out the loop) every time that you do a swap so that you start from the bottom of the array again. This means that you are iterating over data that is already sorted which is inefficient. The bubble sort is slow but faster when it is sorting nearly-sorted data because it can detect when the data is sorted. It should use the swap variable to detect when the data is sorted but although you set this variable you never use it.

You have bastardised the algorithm in an attempt to produce a visualisation. The way you are trying to combine the algorithm will the visualisation will NOT work.

There are 2 alternatives

1) Create a separate thread to perform the sorting and do the visualisation in the main thread. Quite advanced if you are new to programming

2) Perform the sorting algorithm and record all comparisons and swaps. Then you can use this data to perform the visualisation.

I use the second approach to create a sketch that visualised 11 different sorting algorithms. Here it is doing a Bubble Sort (where the biggest values float to the top)

TheApexTheater

@quark Alright, I see where you're coming from now... Originally, I did have a working bubble sort algorithm that was closer to what you're suggesting. The problem was, I was having trouble with the visualization aspect...

If I may, how would you do either of the solutions? I have no idea how threads work (but I'll have to learn someday, so might as well do it while it's relevant), and I'm sort lost with how you'd do #2. Would you simply hold a 2-D array, with each row representing a pair of swaps and each column representing the indexes that have been swapped?

quark

Depending on your experience both options will include some slightly advanced programming topics.

The second option is the easier but rather than a 2D array I suggest creating a class to record the details of a sorting action, and then store these in an array.

I could create a simple sketch to get you started do you want me to?

TheApexTheater

Nah, I think I'm fine from here... Just one question, if I do make a class that contains sorting details and an array to store them, I'd have to calculate the worst case complexity for the size of the array (so as to not waste space), correct?

And this is just extra, but whenever I implement a class within a processing application, I tend to have difficulties with the size() function in setup(), so I put it in settings()... Is this normal?

quark

whenever I implement a class within a processing application, I tend to have difficulties with the size() function in setup(), so I put it in settings()... Is this normal?

No that is not normal it should make no difference on where you put the size() call when implementing classes. The settings method was introduced in Processing 3 and allowed you to use variables in the size. If you use size() in setup then it must be the first statement in that method.

I'd have to calculate the worst case complexity for the size of the array (so as to not waste space), correct?

No you don't want to do that. For the Bubble sort the worst case scenario is n*n so it n = 200 then the array size would have to be 40000. It gets worse as n increases. The best way is to use an ArrayList then convert it an array of the correct size.

For instance a possible class

final int COMPARE = 1;
final int SWAP = 1;

class Action {
  int idx0, idx1;
  int action; // COMPARE or SWAP

  Action(int i0, int i1, int a) {
    idx0 = i0;
    idx1 = i1;
    action = a;
  }
}

Create the ArrayList

ArrayList<Action> actions = new ArrayList<Action>();

Add actions

actions.add(new Action(i, i+1, COMPARE));
actions.add(new Action(i, i+1, SWAP));

Convert to an array
Action[] aa = (Action[])(actions.toArray(new Action[actions.size()]));