Jump to content
  • Advertisement
Sign in to follow this  
stein102

Debug my bubble sort algorithm?

This topic is 902 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm getting an error in my game where my foreground is not rendering on top of my background. My idea is that maybe I messed up my layer sorting method. Does anything look wrong with this?

    public static ArrayList<MapLayer> sortLayers(ArrayList<MapLayer> layers){
        ArrayList<MapLayer> sortedLayers;
        sortedLayers = layers;
        int n = sortedLayers.size();
        MapLayer temp = null;
        
        for(int i = 0; i < n; i++){
            for(int j = 1; j < (n-1); j++){
                if(sortedLayers.get(j-1).getDepth() > sortedLayers.get(j).getDepth()){
                    temp = sortedLayers.get(j-1);
                    sortedLayers.set(j-1,sortedLayers.get(j));
                    sortedLayers.set(j,temp);
                }
            }
        }
    }

Share this post


Link to post
Share on other sites
Advertisement

You never consider "sortedLayers.get((n-1)-1)" versus "sortedLayers.get(n-1)", ie the final entry is never moved.

 

Code is also missing a "return" statement.

 

 

Some other points:

 

"sortedLayers = layers;" has no meaning in Java, you are sharing the entries with the "layers" parameter, so you might as well simply sort "layer" and drop the "sortedLayers" variable.

 

Code becomes easier to read if you move the "temp" variable inside the most inner loop:

MapLayer temp = sortedLayers.get(j-1);
sortedLayers.set(j-1,sortedLayers.get(j));
sortedLayers.set(j,temp);

This clearly says you will not use "temp" outside the "if" around it, so it saves a lot of looking for other uses of the variable.

 

 

 

As for bubble sort itself, there is a lot of room for improvement. I'll start with the more simple ones, and move towards the more complicated ones.

 

1. Instead of doing "n" iterations of the "j" loop, do the "j" loop until nothing changes anymore.

while (true) {
    boolean changed = false;
    for (... j ... ) {
        if (...) {
            ...
            changed = true;
        }
    }
    if (!changed) break; // Nothing changed, no point in looping again.
}

For example, if the array is already sorted, your 'i' loops 'n' times now, while the above quits after the first check.

 

 

2. Your j loop now always increments. That means that bubbling big values down goes fast, but bubbling low values up goes slow. (Try it, write 6, 4, 3, 1 on paper, and do the algorithm manually, writing a new row below it after each swap. You will notice the "6" moves very fast, while the "1" takes ages.)

This can be fixed by also looping over the array high -> low. (ie with a decrementing j).

 

 

There are a couple of other things you can do to speed up, like using a bigger gap between the elements you compare, but in the end, you better just drop the bubble sort, since it has terrible performance.

 

So, what are the alternatives?

 

3. If you have a unique depth, and not too many, you could use a depth array:

// Make list with one element for each depth.
List<MapLayer> depthList = new ArrayList<>();
for (int i = 0; i < MAXDEPTH; i++) depthList.add(null);

In your loop you do

forever {
   ...
   for (int i = 0; i < MAXDEPTH; i++) depthList.set(i, null); // Clear the depth list

   // find maplayers to add, and insert it at "depth" entry in the depth list.
   MapLayer layer = getFooLayer();
   depthList.set(layer.getDepth(), layer);

   // Draw things
   for (MapLayer layer: depthList) {
        if (layer != null) drawLayer(layer);
   }
}

You have one entry for each depth, and instead of throwing it all in a list and then sort them, put them at the right point immediately. You may need to skip some of the layers if there is nothing to draw but that's no problem.

 

 

4. A general purpose solution is to have a set sorted on depth. I am not sure you want to do this at this time, but you'll need a SortedSet, like TreeSet, and a unique depth for each layer (you can get around the latter limitation, but it gets more complicated).

Build a comparator that orders on depth. With these two things, the set does the sorting for you. You just throw in the layers, and then pull them again, and they come out in depth order, since that is how you ordered them.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!