Sorting a string array by Natural Order and ignore spaces

Question

I've found this sample code posted on this forum by Yishai, which works really well. It helps me sort file names found on the disk in a "natural order", i.e. the way humans like to see like:

file1

file2

file3

file11

If it was just the normal (ascii) sorting then the file11 would come after the file1 and before file2

The question is how to improve on this code and make an option that spaces can be ignored, which can be very useful type of sorting when reading file names in a long list like:

file1

file 1

file2

file 3

Here is the code

Collections.sort(myStringArrayList, 
                 new AlphanumComparator(String.CASE_INSENSITIVE_ORDER));



 /*
 * The Alphanum Algorithm is an improved sorting algorithm for strings 
 * containing numbers.  Instead of sorting numbers in ASCII order like 
 * a standard sort, this algorithm sorts numbers in numeric order. 
 * 
 * The Alphanum Algorithm is discussed at http://www.DaveKoelle.com 
 * 
 * 
 * This library is free software; you can redistribute it and/or 
 * modify it under the terms of the GNU Lesser General Public 
 * License as published by the Free Software Foundation; either 
 * version 2.1 of the License, or any later version. 
 * 
 * This library is distributed in the hope that it will be useful, 
 * but WITHOUT ANY WARRANTY; without even the implied warranty of 
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU 
 * Lesser General Public License for more details. 
 * 
 * You should have received a copy of the GNU Lesser General Public 
 * License along with this library; if not, write to the Free Software 
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA 
 * 
 */ 

import java.util.Comparator; 

/** 
 * This is an updated version with enhancements made by Daniel Migowski, 
 * Andre Bogus, and David Koelle 
 * 
 * To convert to use Templates (Java 1.5+): 
 *   - Change "implements Comparator" to "implements Comparator<String>" 
 *   - Change "compare(Object o1, Object o2)" to "compare(String s1, String s2)" 
 *   - Remove the type checking and casting in compare(). 
 * 
 * To use this class: 
 *   Use the static "sort" method from the java.util.Collections class: 
 *   Collections.sort(your list, new AlphanumComparator()); 
 */ 
public class AlphanumComparator implements Comparator<String> 
{ 
    private Comparator<String> comparator = new NaturalComparator(); 

    public AlphanumComparator(Comparator<String> comparator) { 
        this.comparator = comparator; 
    } 

    public AlphanumComparator() { 

    } 

    private final boolean isDigit(char ch) 
    { 
        return ch >= 48 && ch <= 57; 
    } 

    /** Length of string is passed in for improved efficiency (only need to calculate it once) **/ 
    private final String getChunk(String s, int slength, int marker) 
    { 
        StringBuilder chunk = new StringBuilder(); 
        char c = s.charAt(marker); 
        chunk.append(c); 
        marker++; 
        if (isDigit(c)) 
        { 
            while (marker < slength) 
            { 
                c = s.charAt(marker); 
                if (!isDigit(c)) 
                    break; 
                chunk.append(c); 
                marker++; 
            } 
        } else 
        { 
            while (marker < slength) 
            { 
                c = s.charAt(marker); 
                if (isDigit(c)) 
                    break; 
                chunk.append(c); 
                marker++; 
            } 
        } 
        return chunk.toString(); 
    } 

    public int compare(String s1, String s2) 
    { 

        int thisMarker = 0; 
        int thatMarker = 0; 
        int s1Length = s1.length(); 
        int s2Length = s2.length(); 

        while (thisMarker < s1Length && thatMarker < s2Length) 
        { 
            String thisChunk = getChunk(s1, s1Length, thisMarker); 
            thisMarker += thisChunk.length(); 

            String thatChunk = getChunk(s2, s2Length, thatMarker); 
            thatMarker += thatChunk.length(); 

            // If both chunks contain numeric characters, sort them numerically 
            int result = 0; 
            if (isDigit(thisChunk.charAt(0)) && isDigit(thatChunk.charAt(0))) 
            { 
                // Simple chunk comparison by length. 
                int thisChunkLength = thisChunk.length(); 
                result = thisChunkLength - thatChunk.length(); 
                // If equal, the first different number counts 
                if (result == 0) 
                { 
                    for (int i = 0; i < thisChunkLength; i++) 
                    { 
                        result = thisChunk.charAt(i) - thatChunk.charAt(i); 
                        if (result != 0) 
                        { 
                            return result; 
                        } 
                    } 
                } 
            } else 
            { 
                result = comparator.compare(thisChunk, thatChunk); 
            } 

            if (result != 0) 
                return result; 
        } 

        return s1Length - s2Length; 
    } 

    private static class NaturalComparator implements Comparator<String> { 
        public int compare(String o1, String o2) { 
            return o1.compareTo(o2); 
        } 
    }

score 2 · Answer 1 · answered Sep 21 '12 at 18:57

2

Collections.sort(myStringArrayList, new Comparator<String>() {


@Override
        public int compare(String o1, String o2) {
            int temp = o1.length() - o2.length();
            o1 = o1.replaceAll(" ", "");
            o2 = o2.replaceAll(" ", "");
            int compareTo = o1.compareTo(o2);
            if(compareTo == 0){
                return temp;
            }
            else{
                return compareTo;
            }
        }
    });

Comparators can also be used to control the order of certain data structures (such as sorted sets or sorted maps), or to provide an ordering for collections of objects that don't have a natural ordering.

answered Sep 21 '12 at 18:57

JCN

21
1

I've placed this code in NaturalComparator on the bottom of the code in my question, but it does not make a difference, 'level 3' comes before 'level2' instead of after – Lumis Sep 21 '12 at 19:16
@Lumis, try passing JCN's comparator as the comparator in the constructor of NatrualComparator. I expect different results, depending on the types of inputs of the strings. I'm still not clear on how you want to handle the real edge cases here (e.g. "My File 1" vs "MyFile 1" etc.), so I haven't tried for a full answer. – Yishai Sep 23 '12 at 02:47
Because of me initally passing String.CASE_INSENSITIVE_ORDER, NatrualComparator was never called. Your code is working only if I dont use 'temp' and 'if' but just do simle removal of spaces (replaceAll) and compare. Yishai's solution is even more simple... – Lumis Sep 23 '12 at 12:03

Yishai · Accepted Answer · 2012-09-23T14:00:16.887

2

A simple solution which should pass the test of the four cases you presented is to pass the constructor of that same code a custom comparator that looks like this:

 public class SpaceInsensitiveComparator implements Comparator<String> {   
    public int compare(String o1, String o2) {   
        return o1.trim().compareTo(o2.trim());   
    }   
 }

Or for case insensitivity:

 public class SpaceInsensitiveComparator implements Comparator<String> {   
    public int compare(String o1, String o2) {   
        return String.CASE_INSENSITIVE_ORDER.compare(o1.trim(), o2.trim());   
    }   
 }

edited Sep 23 '12 at 14:00

answered Sep 23 '12 at 02:38

Yishai

90,445
31
189
263

It works! But the case insensitive should say String.CASE_INSENSITIVE_ORDER The problem was that the AlphanumComparator had two constructors, so when String.CASE_INSENSITIVE_ORDER was passed the NaturalComparator was not instantiated and was never used. By altering NaturalComparator to use your code and not initially passing String.CASE_INSENSITIVE_ORDER, i've got it working. – Lumis Sep 23 '12 at 11:58

score 0 · Answer 3 · answered Sep 21 '12 at 18:42

0

May be by adding if c != '' inside getChunck() method

if (c != ' ')
{
        chunk.append(c);
}

Above code won't add space to chunk.

answered Sep 21 '12 at 18:42

kosa

65,990
13
130
167

No it does not make a difference – Lumis Sep 21 '12 at 18:59

Sorting a string array by Natural Order and ignore spaces

3 Answers3

Linked