Visualize Bubble Sort

Marhu

Okay I think my mistake is a small but stupid one.. It was pretty simple to create an random array and to use the bubble sort. But now i tried to visualize that array and draw every step, where 2 values are changed, until the end. For that i tried to use lines for the values. The X-Position of the line is the array-Index at that time. The Y-Position or the length of that line is the value at that time. Now I used that code:

int[] list;
int a;

void setup() {

  size(100, 200);
  background(255);

  list = new int[100];
  for (int i=0; i < list.length; i++) {
    list[i] = Math.round(random(0, 200));
  }

  println("Generierte Liste:");
  println(list);

  a=0;
}

void draw() {

  if (a==list.length-1) {
    a=0;
  }

  if (list[a]>list[a+1]) {

    int zwischenspeicher = list[a];
    list[a] = list[a+1];
    list[a+1] = zwischenspeicher;
  }

  a++;

  background(255);
  stroke(0);
  for (int a = 0; a<list.length; a++) {
    line(a, height, a, height-list[a]);
  }
}

I think the sorting algorithm is okay, but I don't know what's wrong with the animation. It's drawing the starting lines and these lines doesn't move, but there are lines coming from the left after and after. So anyone an idea how to change that little mistake? :/

TfGuy44

What you have here is the opposite of a problem; your sketch is a correct visualization of a bubble sort.

The "line" that you see moving from left to right is the the next largest value trickling up to its correct place.

Marhu

Hmm okay do you have an idea how to change that visualization to that?: https://upload.wikimedia.org/wikipedia/commons/5/54/Sorting_bubblesort_anim.gif

TfGuy44

int[] list;
int a;
int max;
boolean done = false;

void setup() {
  size(401, 400);
  background(255);
  list = new int[20];
  for (int i=0; i < list.length; i++) {
    list[i] = i+1; //Math.round(random(0, 200));
  }
  // Shuffle list.
  for ( int i = 0; i < list.length; i++) {
    int r = int(random(list.length));
    int t = list[i];
    list[i] = list[r];
    list[r] = t;
  }
  max = list.length-1;
}

void draw() {
  if ( done ) { 
    return;
  }
  background(255);
  translate(1, 0);
  if (a>=max) {
    a=0;
    max--;
  }
  if (list[a]>list[a+1]) {
    int zwischenspeicher = list[a];
    list[a] = list[a+1];
    list[a+1] = zwischenspeicher;
  }
  a++;
  noStroke();//stroke(0);
  for (int i = 0; i<list.length; i++) {
    fill(196);
    if (i==a) { 
      fill(255, 0, 0);
    }
    if (i>max) { 
      fill(0, 255, 0);
    }
    rect(i*20, height-(20*list[i]), 18, (20*list[i]) );
    fill(0);
    rect(i*20, height-(20*list[i]), 18, 18 );
  }
  if (max == -1) {
    done = true;
  }
}

jeremydouglass

The important thing to understand is that the data / algorithm driving these two -- your first sketch and the wikipedia gif -- is the same. In one you draw lines, in the other rectangles with different colors, but it is the same.

You could instead of drawing lines choose to draw the 20 tallest buildings in the world, and bubble-sort those -- for example looking up a different image file to display based on the values 0-19. The algorithm underneath would be doing the same thing, and updating the screen in the same way.

Marhu

Ok thanks for your help ^^ I think I understand now. In my first version I set the lines too small and there wasn't any space between the lines. That confused me a lot :/

jeremydouglass

Great -- keep in mind that the output is often easy to change, it is the relationships between elements that are important. Here is @TfGuy44's solution again with a simple img added to the drawing step:

int[] list;
int a;
int max;
boolean done = false;
PImage img;

void setup() {
  img = loadImage("https:"+"//processing.org/img/processing3-logo.png");
  img.resize(64,64);
  size(401, 400);
  background(255);
  list = new int[20];
  for (int i=0; i < list.length; i++) {
    list[i] = i+1; //Math.round(random(0, 200));
  }
  // Shuffle list.
  for ( int i = 0; i < list.length; i++) {
    int r = int(random(list.length));
    int t = list[i];
    list[i] = list[r];
    list[r] = t;
  }
  max = list.length-1;
}

void draw() {
  if ( done ) { 
    return;
  }
  background(255);
  translate(1, 0);
  if (a>=max) {
    a=0;
    max--;
  }
  if (list[a]>list[a+1]) {
    int zwischenspeicher = list[a];
    list[a] = list[a+1];
    list[a+1] = zwischenspeicher;
  }
  a++;
  noStroke();//stroke(0);
  for (int i = 0; i<list.length; i++) {
    image(img, i*20, height-(20*list[i]), 18, (20*list[i]));
    fill(196, 128);
    if (i==a) { 
      fill(255, 0, 0, 192);
    }
    if (i>max) { 
      fill(0, 255, 0, 64);
    }
    rect(i*20, height-(20*list[i]), 18, (20*list[i]) );
    fill(0, 64);
    rect(i*20, height-(20*list[i]), 18, 18 );
  }
  if (max == -1) {
    done = true;
  }
}