Loading...
Logo
Processing Forum
Programming Questions
aferriss
aferriss

Sorting pixels with bubble sort

in Programming Questions  •  1 year ago  
Hello,

I'm new to sorting algorithms, and in an effort to keep things as simple as possible for myself, I decided to use a bubble sort to sort the pixels of an image. I know that bubble sort is going to be slow, but I'd like to make it work anyhow. When I run the code below nothing happens. 

Is the problem in my sort, or does it have to do with the way I'm filling the array from the pixels? 

Here is what I've got.

Copy code
  2. PImage img;
  3. int increment= 2;

  5. void setup(){
  6.  img = loadImage("image01.png");
  7.  size (img.width, img.height);
  8.  image(img, 0, 0, width, height);
  9. }

  11. void doSort(){
  12.  loadPixels();
  13.   for (int x = 0; x<((width*height)-(increment+2)); x++){
  14.    bubbleSort(pixels,x, x+increment); 
  15.   }
  16.    updatePixels();
  17.  }

  19. void bubbleSort (int x[], int i, int j){
  20.  // loop through the array
  21.  for (i = 0;  i<x.length-1;i++) {
  22.    if (x[i+1] > x[i]) {
  23.    //swap i and j values
  24.     j = x[i];
  25.     x[i] = x[i+1];
  26.     x[i+1] = j;
  27.    }
  28.  }
  29. }
Thanks in advance for the help!

Replies(9)

calsign
calsign

Re: Sorting pixels with bubble sort

1 year ago
You have a doSort() method, but it is never called... in fact, there is no draw() function!
aferriss
aferriss

Re: Sorting pixels with bubble sort

1 year ago
I am a fool.  Thanks for pointing that out!  It's working fine now, though it is really slow. 
Below is the full code:

Copy code

  3. PImage img;
  4. int increment= 2;

  6. void setup(){
  7.  img = loadImage("trashS.jpg");
  8.  size (img.width, img.height);
  9.  image(img, 0, 0, width, height);
  10. }

  12. void draw(){
  13.  doSort(); 
  14. }

  16. void doSort(){
  17.  loadPixels();
  18.   for (int x = 0; x<((width*height)-(increment+2)); x++){
  19.    bubbleSort(pixels,x, x+increment); 
  20.   }
  21.    updatePixels();
  22.  }

  24. void bubbleSort (int x[], int i, int j){
  25.  // loop through the array
  26.  for (i = 0;  i<x.length-1;i++) {
  27.    if (x[i+1] > x[i]) {
  28.    //swap i and j values
  29.     j = x[i];
  30.     x[i] = x[i+1];
  31.     x[i+1] = j;
  32.    }
  33.  }
  34. }
krumpenj
krumpenj

Re: Re: Sorting pixels with bubble sort

1 year ago
How big is the image you are trying to sort?
krumpenj
krumpenj

Re: Sorting pixels with bubble sort

1 year ago
Agreed regarding doSort().  draw() is not really needed here, though.  

I would like to add a few comments to this:
  1. Conceptually, I enjoyed thinking about your program...sorting the pixels of an image.
  2. It was a little tricky trying to figure out some of your code because your bubbleSort() function had three parameters.  Two of the parameters weren't really necessary.  All you really need to pass to the function is the array itself.  If you need some variables in your bubbleSort() function to help you with the sorting, then declare those as local variables, within the function itself. 
  3. pixels is a one-dimensional array containing all the pixels you want to sort, right?  Since that is the case, it's simpler to rewrite this loop:

Copy code
  1.             for (int x = 0; x<((width*height)-(increment+2)); x++){

            like this:

Copy code
  1.             for (int x = 0; x<pixels.length - 1; x++){

In the end, I tried to make some simple changes to your code to make it a little easier for me to follow.  Here it is :


Copy code
  1. PImage img;
  2. int increment = 2; // not sure this is needed

  4. void setup() {
  5.   img = loadImage("image01.png");
  6.   size (img.width, img.height);
  7.   image(img, 0, 0, width, height);
  8.   doSort();
  9. }

  11. void doSort() {
  12.   loadPixels();
  13.   print(pixels.length);
  14.   for (int x = 0; x<pixels.length - 1; x++) {
  15.     bubbleSort(pixels);
  16.   }
  17.   updatePixels();
  18. }

  20. void bubbleSort (int x[]) {
  21.   // loop through the array
  22.   for (int i = 0;  i<x.length-1;i++) {
  23.     if (x[i+1] > x[i]) {
  24.       //swap i and j values
  25.       int j = x[i];
  26.       x[i] = x[i+1];
  27.       x[i+1] = j;
  28.     }
  29.   }
  30. }






krumpenj
krumpenj

Re: Sorting pixels with bubble sort

1 year ago
Sorry, one more thing.  I see that Processing has its own sort() function.  Have you tried it?  I tried the following (and used reverse() because it seems you wanted to sort from brightest to darkest...without reverse(), it gets sorted darkest to brightest):

Copy code
  1. PImage img;

  3. void setup() {
  4.   img = loadImage("image01.png");
  5.   size (img.width, img.height);
  6.   img.pixels = reverse(sort(img.pixels));
  7.   image(img, 0, 0, width, height);
  8. }
PhiLho
PhiLho

Re: Sorting pixels with bubble sort

1 year ago
Ah, I thought the point was to show the sort in real time, like one sort operation per frame!...

Funny effect:
Copy code
  1. PImage img;
  2.  
  3. void setup()
  4. {
  5.   size(100, 100);
  6.   img = loadImage("G:/Images/map.png");
  7.   image(img, 0, 0);
  8. }
  9.  
  10. void draw()
  11. {
  12.   oneSortStep();
  13. }
  14.  
  15. void oneSortStep()
  16. {
  17.   loadPixels();
  18.   for (int i = 0; i < pixels.length - 1; i++)
  19.   {
  20.     if (blue(pixels[i + 1]) < blue(pixels[i]))
  21.     {
  22.       // Swap pixels
  23.       color c = pixels[i];
  24.       pixels[i] = pixels[i + 1];
  25.       pixels[i + 1] = c;
  26.     }
  27.   }
  28.   updatePixels();
  29. }
I used a small image because it is slow enough!
aferriss
aferriss

Re: Re: Sorting pixels with bubble sort

1 year ago
Thanks Philho, that was cool to see! I have some code that does a similar thing, but quicksort makes it run a little faster :) Changing the increment value can yield some interesting results. 

Copy code
  2. PImage img;
  3. int increment=2;
  4.  
  5. void setup() {
  6.   img = loadImage("image.jpeg");
  7.   size(img.width, img.height);
  8.   image(img, 0, 0);


  11. }
  12. void draw() {
  13.     loadPixels();
  14.   for (int x = 0; x < ((height*width)-(increment+2)); x+=increment) {
  15.     quicksort(pixels, x, x+increment);
  16.   }
  17.   updatePixels();

  19. }
  20.  
  21. int partition(int x[], int left, int right) {
  22.   int i = left;
  23.   int j = right;
  24.   int temp;
  25.   int pivot = x[(left+right)/2];
  26.   while (i <= j) {
  27.     while (x[i] < pivot) {
  28.       i++;
  29.     }
  30.     while (x[j] > pivot) {
  31.       j--;
  32.     }
  33.     if (i <= j) {
  34.       temp = x[i];
  35.       x[i] = x[j];
  36.       x[j] = temp;
  37.       i++;
  38.       j--;
  39.     }
  40.   }
  41.   return i;
  42. }
  43.  
  44. void quicksort(int x[], int left, int right) {
  45.   int index = partition(x, left, right);
  46.   if (left < index - 1) {
  47.     quicksort(x, left, index-1);
  48.   }
  49.   if (index < right) {
  50.     quicksort(x, index, right);
  51.   }
  52. }
JeffThompson
JeffThomp..

Re: Sorting pixels with bubble sort

1 year ago
Hi aferriss, I have spent a lot of time and energy on sorting things over the last few years, much of it in Processing and with images (see: http://www.jeffreythompson.org/RandomHexadecimalValuesSortedNumerically.php).

A few thoughts after you resolve the tech problems:
+ The color model you use will result in really different results - ie: the way RGB is stored vs hex vs HSB.  Generally, HSB is favored for data vis because it gives clean shifts across the spectrum
+ If you really want to geek out, check out the video " Sorting Out Sorting" - it's a 30+ minute early computer animation of different sorting algorithms.  Super nerdy and I love it!
aferriss
aferriss

Re: Re: Sorting pixels with bubble sort

1 year ago
Hi Jeff, Great stuff! 

I'll experiment with HSB and see what I come up with.

The "Sorting Out Sorting" video is awesome, thanks for sharing this!
Top Reply

Statistics

  • 9 Replies
  • 1577  Views
  • 1 Followers

Actions

Related Posts