Public Group

# Debug my bubble sort algorithm?

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

## 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 on other sites

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);


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.

1. 1
2. 2
Rutin
21
3. 3
4. 4
frob
17
5. 5

• 9
• 12
• 9
• 33
• 13
• ### Forum Statistics

• Total Topics
632595
• Total Posts
3007266

×