How does "natural ordering" works for strings

[Emanuele Ghe]

Hi,
I am wondering how natural ordering works for strings.

From the K&B book:
"If you remember that spaces sort before characters and that uppercase
letters sort before lowercase characters, you should be good to go for the exam."

But watching some mocks, I don't think it's enough.

In fact, given the following code:

  
package test;

import java.util.NavigableSet;
import java.util.TreeSet;

public class Collection {

	public static void main(String[] args) {
		
		NavigableSet<String> set = new TreeSet<String>();
		
		set.add("a"); set.add("b");set.add("c");
		set.add("aa"); set.add("bb");set.add("cc");
		set.add("aaa"); set.add("bbb");set.add("ccc");
		set.add("ab"); set.add("ba");set.add("cb");set.add("ac");
		
		System.out.println(set.toString());
		
	}
	
	
}

  

the output is

   
[a, aa, aaa, ab, ac, b, ba, bb, bbb, c, cb, cc, ccc]
 

Why?

Which is the algorithm ?

Thanks.

[Emanuele Ghe]

I found the answer by myself looking at Javadocs for the
String.compareTo method:

Compares two strings lexicographically. The comparison is based on the Unicode value of each character in the strings. The character sequence represented by this String object is compared lexicographically to the character sequence represented by the argument string. The result is a negative integer if this String object lexicographically precedes the argument string. The result is a positive integer if this String object lexicographically follows the argument string. The result is zero if the strings are equal; compareTo returns 0 exactly when the equals(Object) method would return true.

This is the definition of lexicographic ordering. If two strings are different, then either they have different characters at some index that is a valid index for both strings, or their lengths are different, or both. If they have different characters at one or more index positions, let k be the smallest such index; then the string whose character at position k has the smaller value, as determined by using the < operator, lexicographically precedes the other string. In this case, compareTo returns the difference of the two character values at position k in the two string -- that is, the value:

this.charAt(k)-anotherString.charAt(k)


If there is no index position at which they differ, then the shorter string lexicographically precedes the longer string. In this case, compareTo returns the difference of the lengths of the strings -- that is, the value:

this.length()-anotherString.length()

but this still does not explain me why
"aaa" sorts before "b".

I have an idea, but I don't want to influence others, so I hope to get the opinion of other ranchers.

Thanks ;)

[Prithvi Sehgal]

Hi,

If i am not wrong, String implements Comparable.

 

//CASE 1
aaa
b

//Case 2
Prithvi
Beenish

When compareTo method is used, while you are sorting Strings naturally, it's the first character that's being compared
not the whole String.

Both cases,
Beenish will come first and Prithvi second. Because B is smaller then P.

By the way

This is the definition of lexicographic ordering. If two strings are different, then either they have different characters at some index that is a valid index for both strings, or their lengths are different, or both. If they have different characters at one or more index positions, let k be the smallest such index; then the string whose character at position k has the smaller value, as determined by using the < operator, lexicographically precedes the other string. In this case, compareTo returns the difference of the two character values at position k in the two string -- that is, the value:

This answers your question. Ain't it mate?

What is the reason inside your mind? I am also curious to know.

Happy Preparation and good to have you back.

[Paul Clapham]

You don't need the opinions of other ranchers. Opinions are useless when you actually have a description of how things work. And you posted that description yourself already. Read the paragraph starting

This is the definition of lexicographic ordering.

and apply it to your question.

[Emanuele Ghe]

Well from the definition isn't cristal clear, but I think that the natural ordering for strings means that they
are ordered in this way:
(I'll use pseudo code)

s1.compareTo(s2):

if(s1.length() == s2.length() ) {
Char c1 = s1.charAr(0);
Char c2 = s2.charAt(0);
if(c1 != c2)
return c1.compareTo(c2);
else
//compare the other chars until the end or until one couple of chars are !=
} else {
//compare first character of both, and, if equal, go to the second character.
//if you reach the end of the shortest string, and the shortest has all chars euquals to the longest, the shortest comes first.
}

What do you think ?

[Prithvi Sehgal]

Yes Eman,

That's what the paragraph was saying. :D

Best Regards,

[Emanuele Ghe]

Prithvi Sehgal wrote:Yes Eman,

That's what the paragraph was saying. :D

Best Regards,

Yes, I realized that when I pressed the "submit" button.