Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.java.programmer > #33408 > unrolled thread

Java sort

Back to article view | Back to comp.lang.java.programmer

Contents

  Java sort Eric Douglas <e.d.programmer@gmail.com> - 2015-12-28 12:08 -0800
    Re: Java sort Eric Sosman <esosman@comcast-dot-net.invalid> - 2015-12-28 15:35 -0500
      Re: Java sort Eric Douglas <e.d.programmer@gmail.com> - 2015-12-28 12:49 -0800
        Re: Java sort Eric Douglas <e.d.programmer@gmail.com> - 2015-12-28 13:02 -0800
          Re: Java sort Eric Douglas <e.d.programmer@gmail.com> - 2015-12-28 13:16 -0800
            Re: Java sort Arne Vajhøj <arne@vajhoej.dk> - 2015-12-28 22:49 -0500
        Re: Java sort Eric Sosman <esosman@comcast-dot-net.invalid> - 2015-12-28 17:55 -0500
        Re: Java sort leif.roar@dimnakorr.com - 2015-12-29 01:20 -0600
    Re: Java sort Andreas Leitgeb <avl@logic.at> - 2015-12-28 23:17 +0000
      Re: Java sort Eric Douglas <e.d.programmer@gmail.com> - 2015-12-29 05:41 -0800
    Re: Java sort Arne Vajhøj <arne@vajhoej.dk> - 2015-12-28 22:47 -0500
    Re: Java sort Jeff Higgins <jeff@invalid.invalid> - 2015-12-29 15:03 +0000

#33408 — Java sort

My program called java.io.File.listFiles(), then java.util.Collections.sort().
My results:
1.pdf
10.pdf
100.pdf
2.pdf
3.pdf
Windows Explorer's results:
1.pdf
2.pdf
3.pdf
10.pdf
100.pdf

I asked Google and it says Windows Explorer uses this:
https://msdn.microsoft.com/en-us/library/bb759947(VS.85).aspx
I asked Google for a Java equivalent and I'm not finding an easy answer.  Is there one I'm missing?  I hate to reinvent a wheel.

[toc] | [next] | [standalone]

#33409

On 12/28/2015 3:08 PM, Eric Douglas wrote:
> My program called java.io.File.listFiles(), then java.util.Collections.sort().
> My results:
> 1.pdf
> 10.pdf
> 100.pdf
> 2.pdf
> 3.pdf
> Windows Explorer's results:
> 1.pdf
> 2.pdf
> 3.pdf
> 10.pdf
> 100.pdf
>
> I asked Google and it says Windows Explorer uses this:
> https://msdn.microsoft.com/en-us/library/bb759947(VS.85).aspx
> I asked Google for a Java equivalent and I'm not finding an easy answer.  Is there one I'm missing?  I hate to reinvent a wheel.

     Nothing that comes in Java's standard stuff, as far as
I know.  But you might want

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

-- 
esosman@comcast-dot-net.invalid
"Don't be afraid of work. Make work afraid of you." -- TLM

[toc] | [prev] | [next] | [standalone]

#33410

On Monday, December 28, 2015 at 3:35:41 PM UTC-5, Eric Sosman wrote:
>      Nothing that comes in Java's standard stuff, as far as
> I know.  But you might want
> 
> http://sourcefrog.net/projects/natsort/

Is there Java code in that link?  I don't see it.
So far I only found 2 results and they give a different order than Windows, at least the default order for Windows 8.1.
https://github.com/paour/natorder
http://www.davekoelle.com/files/AlphanumComparator.java

That first one even includes an example:
String[] strings = new String[] { "1-2", "1-02", "1-20", "10-20", "fred", "jane", "pic01", "pic2", "pic02", "pic02a", "pic3", "pic4", "pic 4 else", "pic 5", "pic05", "pic 5", "pic 5 something", "pic 6", "pic   7", "pic100", "pic100a", "pic120", "pic121", "pic02000", "tom", "x2-g8", "x2-y7", "x2-y08", "x8-y8" };

Their result:
Sorted: [1-02, 1-2, 1-20, 10-20, fred, jane, pic01, pic02, pic2, pic02a, pic3, pic4, pic 4 else, pic05, pic 5, pic 5, pic 5 something, pic 6, pic   7, pic100, pic100a, pic120, pic121, pic02000, tom, x2-g8, x2-y7, x2-y08, x8-y8]
Windows (I wrote those out as empty files):
[1-02, 1-2, 1-20, 10-20, fred, jane, pic   7, pic 4 else, pic 5, pic 5 something, pic 6, pic01, pic02, pic02a, pic2, pic3, pic4, pic05, pic100, pic100a, pic120, pic121, pic02000, tom, x2-g8, x2-y7, x2-y08, x8-y8]

[toc] | [prev] | [next] | [standalone]

#33413

On Monday, December 28, 2015 at 3:49:47 PM UTC-5, Eric Douglas wrote:
> On Monday, December 28, 2015 at 3:35:41 PM UTC-5, Eric Sosman wrote:
> >      Nothing that comes in Java's standard stuff, as far as
> > I know.  But you might want
> > 
> > http://sourcefrog.net/projects/natsort/
> 
> Is there Java code in that link?  I don't see it.
> So far I only found 2 results and they give a different order than Windows, at least the default order for Windows 8.1.
> https://github.com/paour/natorder
> http://www.davekoelle.com/files/AlphanumComparator.java
> 
> That first one even includes an example:
> String[] strings = new String[] { "1-2", "1-02", "1-20", "10-20", "fred", "jane", "pic01", "pic2", "pic02", "pic02a", "pic3", "pic4", "pic 4 else", "pic 5", "pic05", "pic 5", "pic 5 something", "pic 6", "pic   7", "pic100", "pic100a", "pic120", "pic121", "pic02000", "tom", "x2-g8", "x2-y7", "x2-y08", "x8-y8" };
> 
> Their result:
> Sorted: [1-02, 1-2, 1-20, 10-20, fred, jane, pic01, pic02, pic2, pic02a, pic3, pic4, pic 4 else, pic05, pic 5, pic 5, pic 5 something, pic 6, pic   7, pic100, pic100a, pic120, pic121, pic02000, tom, x2-g8, x2-y7, x2-y08, x8-y8]
> Windows (I wrote those out as empty files):
> [1-02, 1-2, 1-20, 10-20, fred, jane, pic   7, pic 4 else, pic 5, pic 5 something, pic 6, pic01, pic02, pic02a, pic2, pic3, pic4, pic05, pic100, pic100a, pic120, pic121, pic02000, tom, x2-g8, x2-y7, x2-y08, x8-y8]

I also tried the Comparator in the last post in this thread
http://stackoverflow.com/questions/1262239/natural-sort-order-string-comparison-in-java-is-one-built-in
I think it's closer, though a couple results are still out of place. It got some right the other one got wrong so it seems they're both half right.
Sorted: [1-2, 1-02, 1-20, 10-20, fred, jane, pic   7, pic 4 else, pic 5 something, pic 5, pic 5, pic 6, pic01, pic2, pic02, pic02a, pic3, pic4, pic05, pic100a, pic100, pic120, pic121, pic02000, tom, x2-g8, x2-y7, x2-y08, x8-y8]

[toc] | [prev] | [next] | [standalone]

#33414

On Monday, December 28, 2015 at 4:02:52 PM UTC-5, Eric Douglas wrote:
> On Monday, December 28, 2015 at 3:49:47 PM UTC-5, Eric Douglas wrote:
> > On Monday, December 28, 2015 at 3:35:41 PM UTC-5, Eric Sosman wrote:
> > >      Nothing that comes in Java's standard stuff, as far as
> > > I know.  But you might want
> > > 
> > > http://sourcefrog.net/projects/natsort/
> > 
> > Is there Java code in that link?  I don't see it.
> > So far I only found 2 results and they give a different order than Windows, at least the default order for Windows 8.1.
> > https://github.com/paour/natorder
> > http://www.davekoelle.com/files/AlphanumComparator.java
> > 
> > That first one even includes an example:
> > String[] strings = new String[] { "1-2", "1-02", "1-20", "10-20", "fred", "jane", "pic01", "pic2", "pic02", "pic02a", "pic3", "pic4", "pic 4 else", "pic 5", "pic05", "pic 5", "pic 5 something", "pic 6", "pic   7", "pic100", "pic100a", "pic120", "pic121", "pic02000", "tom", "x2-g8", "x2-y7", "x2-y08", "x8-y8" };
> > 
> > Their result:
> > Sorted: [1-02, 1-2, 1-20, 10-20, fred, jane, pic01, pic02, pic2, pic02a, pic3, pic4, pic 4 else, pic05, pic 5, pic 5, pic 5 something, pic 6, pic   7, pic100, pic100a, pic120, pic121, pic02000, tom, x2-g8, x2-y7, x2-y08, x8-y8]
> > Windows (I wrote those out as empty files):
> > [1-02, 1-2, 1-20, 10-20, fred, jane, pic   7, pic 4 else, pic 5, pic 5 something, pic 6, pic01, pic02, pic02a, pic2, pic3, pic4, pic05, pic100, pic100a, pic120, pic121, pic02000, tom, x2-g8, x2-y7, x2-y08, x8-y8]
> 
> I also tried the Comparator in the last post in this thread
> http://stackoverflow.com/questions/1262239/natural-sort-order-string-comparison-in-java-is-one-built-in
> I think it's closer, though a couple results are still out of place. It got some right the other one got wrong so it seems they're both half right.
> Sorted: [1-2, 1-02, 1-20, 10-20, fred, jane, pic   7, pic 4 else, pic 5 something, pic 5, pic 5, pic 6, pic01, pic2, pic02, pic02a, pic3, pic4, pic05, pic100a, pic100, pic120, pic121, pic02000, tom, x2-g8, x2-y7, x2-y08, x8-y8]

The answer in the middle of that thread, by Olivier Oudot, is closer - still not sorting numerics with leading zeroes first.

[toc] | [prev] | [next] | [standalone]

#33425

On 12/28/2015 4:16 PM, Eric Douglas wrote:
> On Monday, December 28, 2015 at 4:02:52 PM UTC-5, Eric Douglas
> wrote:
>> On Monday, December 28, 2015 at 3:49:47 PM UTC-5, Eric Douglas
>> wrote:
>>> On Monday, December 28, 2015 at 3:35:41 PM UTC-5, Eric Sosman
>>> wrote:
>>>> Nothing that comes in Java's standard stuff, as far as I know.
>>>> But you might want
>>>>
>>>> http://sourcefrog.net/projects/natsort/
>>>
>>> Is there Java code in that link?  I don't see it. So far I only
>>> found 2 results and they give a different order than Windows, at
>>> least the default order for Windows 8.1.
>>> https://github.com/paour/natorder
>>> http://www.davekoelle.com/files/AlphanumComparator.java
>>>
>>> That first one even includes an example: String[] strings = new
>>> String[] { "1-2", "1-02", "1-20", "10-20", "fred", "jane",
>>> "pic01", "pic2", "pic02", "pic02a", "pic3", "pic4", "pic 4 else",
>>> "pic 5", "pic05", "pic 5", "pic 5 something", "pic 6", "pic   7",
>>> "pic100", "pic100a", "pic120", "pic121", "pic02000", "tom",
>>> "x2-g8", "x2-y7", "x2-y08", "x8-y8" };
>>>
>>> Their result: Sorted: [1-02, 1-2, 1-20, 10-20, fred, jane, pic01,
>>> pic02, pic2, pic02a, pic3, pic4, pic 4 else, pic05, pic 5, pic 5,
>>> pic 5 something, pic 6, pic   7, pic100, pic100a, pic120, pic121,
>>> pic02000, tom, x2-g8, x2-y7, x2-y08, x8-y8] Windows (I wrote
>>> those out as empty files): [1-02, 1-2, 1-20, 10-20, fred, jane,
>>> pic   7, pic 4 else, pic 5, pic 5 something, pic 6, pic01, pic02,
>>> pic02a, pic2, pic3, pic4, pic05, pic100, pic100a, pic120, pic121,
>>> pic02000, tom, x2-g8, x2-y7, x2-y08, x8-y8]
>>
>> I also tried the Comparator in the last post in this thread
>> http://stackoverflow.com/questions/1262239/natural-sort-order-string-comparison-in-java-is-one-built-in
>>
>>
 >> I think it's closer, though a couple results are still out of place.
 >> It got some right the other one got wrong so it seems they're both
 >> half right.
>> Sorted: [1-2, 1-02, 1-20, 10-20, fred, jane, pic   7, pic 4 else,
>> pic 5 something, pic 5, pic 5, pic 6, pic01, pic2, pic02, pic02a,
>> pic3, pic4, pic05, pic100a, pic100, pic120, pic121, pic02000, tom,
>> x2-g8, x2-y7, x2-y08, x8-y8]
>
> The answer in the middle of that thread, by Olivier Oudot, is closer
> - still not sorting numerics with leading zeroes first.

This is a much harder problem than your first post indicated.

But I will suggest something similar.

One attempt:

import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class VerySpecialSort {
	public static interface Normalizer {
		public String convert(String s);
	}
	public static class WindowsHack implements Normalizer {
		private void xappend(StringBuilder sb, StringBuilder tmp) {
			if(tmp.length() > 0) {
				sb.append(String.format("%010d%c", Integer.parseInt(tmp.toString()), 
tmp.charAt(0) == '0' ? 'A' : 'B'));
				tmp.delete(0, tmp.length());
			}
		}
		@Override
		public String convert(String s) {
			StringBuilder sb = new StringBuilder();
			StringBuilder tmp = new StringBuilder();
			for(char c : s.toCharArray()) {
				if(Character.isDigit(c)) {
					tmp.append(c);
				} else if(c == ' ' || c == '-' || Character.isUpperCase(c)) {
					xappend(sb, tmp);
					sb.append(c);
				} else if(Character.isLowerCase(c)) {
					xappend(sb, tmp);
					sb.append(Character.toUpperCase(c));
				}
			}
			xappend(sb, tmp);
			return sb.toString();
		}
	}
	public static class NormalizerComparator implements Comparator<String> {
		private Normalizer norm;
		public NormalizerComparator(Normalizer norm) {
			this.norm = norm;
		}
		@Override
		public int compare(String s1, String s2) {
			return norm.convert(s1).compareTo(norm.convert(s2));
		}
	}
	public static void main(String[] args) {
		List<String> lst = Arrays.asList("1-2", "1-02", "1-20", "10-20", 
"fred", "jane", "pic01", "pic2", "pic02", "pic02a", "pic3", "pic4", "pic 
4 else", "pic 5", "pic05", "pic 5 something", "pic 6", "pic   7", 
"pic100", "pic100a", "pic120", "pic121", "pic02000", "tom", "x2-g8", 
"x2-y7", "x2-y08", "x8-y8" );
		System.out.println(lst);
		Collections.sort(lst);
		System.out.println(lst);
		Collections.sort(lst, new NormalizerComparator(new WindowsHack()));
		System.out.println(lst);
		List<String> res = Arrays.asList("1-02", "1-2", "1-20", "10-20", 
"fred", "jane", "pic   7", "pic 4 else", "pic 5", "pic 5 something", 
"pic 6", "pic01", "pic02", "pic02a", "pic2", "pic3", "pic4", "pic05", 
"pic100", "pic100a", "pic120", "pic121", "pic02000", "tom", "x2-g8", 
"x2-y7", "x2-y08", "x8-y8");
		System.out.println(res);
	}
}

Arne

[toc] | [prev] | [next] | [standalone]

#33421

On 12/28/2015 3:49 PM, Eric Douglas wrote:
> On Monday, December 28, 2015 at 3:35:41 PM UTC-5, Eric Sosman wrote:
>>       Nothing that comes in Java's standard stuff, as far as
>> I know.  But you might want
>>
>> http://sourcefrog.net/projects/natsort/
>
> Is there Java code in that link?  I don't see it.

     The text says so, and gives a link -- but now that I click
on it, I see that it's been 404'ed.  However, when I duckduckgo[*]
the cited class name, I find

http://www.java2s.com/Code/Java/Collections-Data-Structure/NaturalOrderComparator.htm

... which is still alive.  For how much longer, no one can say:
Move Quickly!

     [*] Like googling, but with less snoopiness.

-- 
esosman@comcast-dot-net.invalid
"Don't be afraid of work. Make work afraid of you." -- TLM

[toc] | [prev] | [next] | [standalone]

#33426

Eric Douglas <e.d.programmer@gmail.com> wrote:
> 
> Is there Java code in that link?  I don't see it.
> So far I only found 2 results and they give a different order 
> than Windows, at least the default order for Windows 8.1.
> https://github.com/paour/natorder
> http://www.davekoelle.com/files/AlphanumComparator.java

Is there any reason your program must match Window's sort
order exactly?

-- 
Leif Roar Moldskred

[toc] | [prev] | [next] | [standalone]

#33423

Stefan Ram <ram@zedat.fu-berlin.de> wrote:
>   This might actually be a little bit off-topic here,
>   but I just tried this in Windows explorer: I created
>   four files and had Windows explorer sort them by name.
>   The outcome:
> 4
> 33333333333333333
> 11111111111111111111111111111111111111111111111111111111111111111111111111111
> 22222222222222222222222222222222222222
>   It is not obvious by which meaning of the word »sorted«
>   this is now »sorted«.

I don't know what is the algorithm used, but I can think of some 
algorithm that would yield that order:

Namely, if it only uses as many digits as fit into a long (64bit)

Rename the 3333... file to append 2 more "3"s, and I'd predict it'll
get sorted to bottom (after a refresh). I don't have Windows here, so
can't test myself.

[toc] | [prev] | [next] | [standalone]

#33427

On Monday, December 28, 2015 at 6:20:04 PM UTC-5, Andreas Leitgeb wrote:
> >   This might actually be a little bit off-topic here,
> >   but I just tried this in Windows explorer: I created
> >   four files and had Windows explorer sort them by name.
> >   The outcome:
> > 4
> > 33333333333333333
> > 11111111111111111111111111111111111111111111111111111111111111111111111111111
> > 22222222222222222222222222222222222222
> >   It is not obvious by which meaning of the word »sorted«
> >   this is now »sorted«.
> 
> I don't know what is the algorithm used, but I can think of some 
> algorithm that would yield that order:
> 
> Namely, if it only uses as many digits as fit into a long (64bit)
> 
> Rename the 3333... file to append 2 more "3"s, and I'd predict it'll
> get sorted to bottom (after a refresh). I don't have Windows here, so
> can't test myself.

Correct.  That file named 4 gets sorted between a file named 1-20 and a file named 10-20 which all come before the file with the 1s.  That file with the 3s does sort after that file with the 2s if you add 2 more 3s.

In that particular case perhaps the simple DOS (Command Prompt) alpha sort makes more sense?  It now seems likely neither method would give the results a human would, so perhaps I should use a hybrid sort that is not quite what Windows Explorer would do but still much better than the DOS command.  Command Prompt sorting, using Collections.sort(), gets annoying when 96.pdf comes between 959.pdf and 960.pdf.

[toc] | [prev] | [next] | [standalone]

#33424

On 12/28/2015 3:08 PM, Eric Douglas wrote:
> My program called java.io.File.listFiles(), then java.util.Collections.sort().
> My results:
> 1.pdf
> 10.pdf
> 100.pdf
> 2.pdf
> 3.pdf
> Windows Explorer's results:
> 1.pdf
> 2.pdf
> 3.pdf
> 10.pdf
> 100.pdf
>
> I asked Google and it says Windows Explorer uses this:
> https://msdn.microsoft.com/en-us/library/bb759947(VS.85).aspx
> I asked Google for a Java equivalent and I'm not finding an easy answer.  Is there one I'm missing?  I hate to reinvent a wheel.

I think you will have to write some custom code.

The key point must be to isolate the file name to numeric value logic.

One suggestion:

import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class SpecialSort {
	public static interface Evaluator {
		public int value(String s);
	}
	public static class StartingInteger implements Evaluator {
		private static final Pattern p = Pattern.compile("\\d+");
		@Override
		public int value(String s) {
			Matcher m = p.matcher(s);
			if(m.find()) {
				return Integer.parseInt(m.group());
			} else {
				return 0;
			}
		}
	}
	public static class ValueComparator implements Comparator<String> {
		private Evaluator eval;
		public ValueComparator(Evaluator eval) {
			this.eval = eval;
		}
		@Override
		public int compare(String s1, String s2) {
			return eval.value(s1) - eval.value(s2);
		}
	}
	public static void main(String[] args) {
		List<String> lst = Arrays.asList("1.pdf", "10.pdf", "100.pdf", 
"2.pdf", "3.pdf" );
		System.out.println(lst);
		Collections.sort(lst);
		System.out.println(lst);
		Collections.sort(lst, new ValueComparator(new StartingInteger()));
		System.out.println(lst);
	}
}

Arne

[toc] | [prev] | [next] | [standalone]

#33429

On Mon, 28 Dec 2015 12:08:55 -0800, Eric Douglas wrote:

> My program called java.io.File.listFiles(), then
> java.util.Collections.sort().
> My results:
> 1.pdf 10.pdf 100.pdf 2.pdf 3.pdf Windows Explorer's results:
> 1.pdf 2.pdf 3.pdf 10.pdf 100.pdf
> 
> I asked Google and it says Windows Explorer uses this:
> https://msdn.microsoft.com/en-us/library/bb759947(VS.85).aspx I asked
> Google for a Java equivalent and I'm not finding an easy answer.  Is
> there one I'm missing?  I hate to reinvent a wheel.

Not that I'm aware of.

I'd like to find a free page number sorter.
i.pdf
ii.pdf
iii.pdf
...
xiv.pdf
1.pdf
2.pdf
3.pdf
...
565.pdf
If you happen across one in your search, I'd appreciate a pointer.
Especially if I could plug it into a Gnome based file manager.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.java.programmer

csiph-web