Sort ArrayList

Question

Hi Experts,

Here is a simple sorting program of an ArrayList:

ArrayList<String> list = new ArrayList<String>();

list.add("1_Update");
list.add("11_Add");
list.add("12_Delete");
list.add("2_Create");

Collections.sort(list);
for (String str : list) {
  System.out.println(str.toString());
}

I was expecting the output of this program as:

1_Update
2_Create
11_Add
12_Delete

But when I run this program I am getting output as:

11_Add
12_Delete
1_Update
2_Create

Why is this and how do I get the ArrayList to sort as shown in the expected output?

Answer 1

yeah it is doing string comparisons not integer.

Answer 2

Try looking up "Natural Order Comparison"

http://sourcefrog.net/projects/natsort/

Answer 3

Because its sorting as a String

ASCII Table

Answer 4

It is sorted as text (alphabetically), not as numbers.

Answer 5

The Collections.sort() method's docs says:

Sorts the specified list into ascending order, according to the natural ordering of its elements.

Which means for Strings that you are going to get the list in alphabetic order. The String 11_assign_privileges.sql comes before the string 1_create_table.sql and 12_07_insert_static_data.sql comes before 1_create_table.sql etc. So the program is working as expected.

Answer 6

Because strings are sorted in a alphabetic ordering and the underscore character is after characters for numbers. You have to provide a comparator implementing "Natural Order" to achieve desired result.

Answer 7

When you sort this type of data as a string, it is comparing the characters themselves, including the digits. All of the string that begin with "1", for example, will end up together. So the order ends up similar to this...

1 10 100 2 20 200

At no point does the sort "realize" that you are assigning meaning to subsets of the string, such as the variable length numbers at the front of the string. When sorting numbers as strings, padding to the left with zeros as much as required to cover the largest number can help, but it does not really solve the problem when you don't control the data, as in your example. In that case, the sort would be...

001 002 010 020 100 200

Answer 8

The string compare algorithm compare each character at a time. 1 sorts before 2. It doesn't matter that it is followed by a 1 or a 2.

So 100 would sort before 2. If you don't want this behavior, you need a compare algorithm that handles this case.

Answer 9

As others have stated, the elements will be sorted alphabetically by default. The solution is define a concrete java.util.Comparator class and pass it as a second argument to the sort method. Your comparator will need to parse out the leading integers from the strings and compare them.

Answer 10

It is doing a lexicographic comparison. It compares the first character in each string sorting them. It then compares the second string of those with the same first charater. When it compares the '_' character to a number, it is greater in value than any single number character just like 8 > 7 and a > 9. Remember it is doing a character comparison and not a numeric comparison.

There are ways to implement your own custom sorting routing which may be better than renaming your script names.

If renaming your script names is an option, this may allow other script tools to be used. One format may be

01_create_table.sql
02_create_index.sql
11_assign_privileges.sql

By keeping your first two digits to two characters, the lexicographic comparison will work.

Answer 11

To have Collection.sort() sort arbitrarily you can use

Collections.sort(List list, Comparator c)

Then simply implement a Comparator that splits the string and sorts first based on the number and then on the rest or however you want it to sort.

Answer 12

There's a very nice natural order comparator here http://weblogs.java.net/blog/skelvin/archive/2006/01/natural_string.html

Answer 13

Everyone has already pointed out that the explanation is that your strings are sorting as strings, and a number have already directed your attention to Natural Order string comparison. I'll just add that it's a great exercise to write that comparator yourself, and a great opportunity to practice test-driven development. I've used it to demonstrate TDD at Code Camp; slides & code are here.

Answer 14

As stated above, you are looking for a Comparator implementation that implements a natural sort. Jeff Atwood wrote an excellent post on natural sorting some time ago - it's well worth a read.

If you're looking for a Java implementation I have found this one to be useful: http://www.davekoelle.com/alphanum.html

Answer 15

You could write a custom comparator:

Collections.sort(list, new Comparator<String>() {
    public int compare(String a, String b) {
        return Integer.signum(fixString(a) - fixString(b));
    }
    private int fixString(string in) {
        return Integer.parseInt(in.substring(0, in.indexOf('_')));
    }
});