Sorting using comparable

Question

Intro

My code to do a custom sort by using Comparable is not work the way I want it to. I'm basically taking an Array of directories and sorting them by:

1. First number of directories, the fewer comes first.
2. If it's a tie alphabetically.

The problem

An example of an input you be:

["/", "/usr/", "/usr/local/", "/usr/local/bin/", "/games/", "/games/snake/", "/homework/", "/temp/downloads/" ]

Which should return this:

["/", "/games/", "/homework/", "/usr/", "/games/snake/", "/temp/downloads/", "/usr/local/", "/usr/local/bin/" ]

But for some reason my code is return this:

["/", "/usr/", "/games/", "/homework/", "/usr/local/", "/games/snake/", "/usr/local/bin/", "/temp/downloads/" ]

My code [edited with comments]

import java.util.*;

public class Dirsort { public String[] sort(String[] dirs) {
    //Creates Array list containing Sort object
    ArrayList<Sort> mySort = new ArrayList<Sort>();
    //Loop that gets the 3 needed values for sorting
        for (String d: dirs){
            String [] l = d.split("/");//String array for alphabetical comparison
            int di = d.length();//Length of array for sorting by number of directories
            mySort.add(new Sort(di,l,d));//adds Sort object to arraylist (note d (the entire directory) is needed for the toString)
        }
        Collections.sort(mySort);//sorts according to compareTo
        String [] ans = new String [mySort.size()];//Creates a new string array that will be returned
        int count = 0;//to keep track of where we are in the loop for appending
        for (Sort s: mySort){
            ans[count] = s.toString();
            count++;
        }
        return ans;
    }
    class Sort implements Comparable<Sort>{
        private int d;//number of directories
        private String [] arr;//array of strings of names of directories
        private String dir;//full directory as string for toString

        //Constructor
        public Sort(int myD, String [] myArr, String myDir){
            d = myD;
            arr = myArr;
            dir = myDir;
        }

        //toString
        public String toString(){
            return dir;
        }

        @Override
        public int compareTo(Sort arg0) {
            // TODO Auto-generated method stub
            //If they are the same return 0
            if (this.equals(arg0)){
                return 0;
            }

            //if the directories are empty
            if("/".equals(arg0.dir)){
                return 1;
            }
            if ("/".equals(this.dir)){
                return -1;
            }

            //If they are not the same length the shorter one comes first
            if (this.d != arg0.d){
                return this.d - arg0.d;
            }

            //If they are the same length, compare them alphabetically
            else{
                for (int i = 0; i < arg0.d; i++){
                    if (!this.arr[i].equals(arg0.arr[i])){
                        return this.arr[i].compareTo(arg0.arr[i]);
                    }
                }
            }
            return 0;
        }   
    }
}

Answer 1

The bug is here:

for (String d: dirs){
    String [] l = d.split("/");

    int di = d.length(); // <- here

    mySort.add(new Sort(di,l,d));
}

Because there you are comparing the length of the entire directory String, not the number of 'folders' in the directory. That's why "/usr/" comes before "/homework/", for example, because:

"/usr/".length() == 5
"/homework/".length() == 10

I believe what you wanted was this, using the length of the split:

int di = l.length;

Then the output is:

/
/games/
/homework/
/usr/
/games/snake/
/temp/downloads/
/usr/local/
/usr/local/bin/

There's another small bug though (possibly), which is that calling split on a String that starts with the delimiter will result in an empty String at the beginning.

IE:

"/usr/".split("/") == { "", "usr" }

So you might want to do something about that. Though here it means that all of them start with the empty String so it doesn't end up with an effect on the way you're doing the comparison.

And as a side note, it's also true what @JBNizet is suggesting that giving your variables more meaningful names helps a lot here. fullDir.length() and splitDir.length would have made this much easier to spot (and it may have never happened in the first place).