up vote 5 down vote favorite
1

Recently when I was working with JavaScript "sort()" function, I found in one of the tutorials that this function does not sort the numbers properly. Instead to sort numbers, a function must be added that compares numbers, like the following code:-

<script type="text/javascript">
function sortNumber(a,b)
{
    return a - b;
}

var n = ["10", "5", "40", "25", "100", "1"];
document.write(n.sort(sortNumber));
</script>

The output then comes as:-

1,5,10,25,40,100

Now what I didn't understand is that why is this occurring & can anybody please tell in details as to what type of algorithm is being used in this "sort()" function? This is because for any other language, I didn't find this problem where the function didn't sort the numbers correctly.

Any help is greatly appreciated.

share|improve this question
92% accept rate
1  
The actual sort algorithm used varies depending on the javascript engine implemented by the browser (see stackoverflow.com/questions/234683/… for details) but all still need to be fed the correct datatype to identify whether to sort by numeric value or by string value – Mark Baker Aug 6 '10 at 11:46
your example is not sorting numbers, it's sorting strings – brad Aug 6 '10 at 13:20
The function sortNumber you pass to sort tell it how to compare two elements. – Satoru.Logic Aug 6 '10 at 13:31
Can anybody please suggest what to do as I found 3 answers very much perfect for me w.r.t. my question? I feel like making this question as a CW one. – Knowledge Craving Aug 10 '10 at 11:54
1  
@KC IMHO, just mark the most up voted as the answer in this case – Giu Aug 11 '10 at 11:08
show 1 more comment
feedback

7 Answers

up vote 10 down vote accepted

Well, if you are sorting the following list, it contains only strings:

var n = ["10", "5", "40", "25", "100", "1"];

So I would expect any language would compare them as strings, thus resulting in a sort order of:

var n = ["1", "10", "100", "25", "40", "5"];

Which necessitates your code to use a custom sort (as you have done) to cast the strings back to integers for the purposes of sorting.

Edit

As Pointy mentioned, by default the JavaScript sort() method sorts elements alphabetically, including numbers:

By default, the sort() method sorts the elements alphabetically and ascending. However, numbers will not be sorted correctly (40 comes before 5). To sort numbers, you must add a function that compare numbers.

Simply amazing... so a custom sort is required even for an array of integers.

share|improve this answer
2  
In case it's unclear to the OP why a string-comparison would get this result, think of each digit in the number as if it were instead a letter of the alphabet, and put the "words" into alphabetical order. (This generalisation of "alphabetical order" to arbitrary strings is called "lexicographic order") – David Aug 6 '10 at 11:46
2  
The default sort comparator always sorts by string values unless a comparator is provided. It does that regardless of the actual types of the array elements. – Pointy Aug 6 '10 at 12:49
feedback
up vote 5 down vote

Javascript's sort sorts by default lexicographical, alphabetical. Thus as I understand it every element is treated as a string. The internal sorting algorithm is most probably quicksort or mergesort. To be able to use quicksort you need to be able to relate elements to each other, is a bigger than b? In the string case this ordering is already implemented.

Since you might want to sort your custom datatypes etc. you can provide a functional defining how to order two elements.

From your example your functional determines the order of two numbers a and b. Javascript sort then uses your function telling sort how to order the elements.

Turns out that mergesort is used by Mozilla, look at: http://stackoverflow.com/questions/234683/javascript-array-sort-implementation

share|improve this answer
feedback
up vote 5 down vote

The problem lies with the use of strings to represent numbers, which the sort function unfortunately does as default. Strings are sorted alphabetically. The comparison function in your code just forces the strings to be evaluated as numbers.

I'd consider it very bad API design that the sort function defaults to treating the elements as strings, but it may be necessary given JavaScript's loose type system..

share|improve this answer
No, in fact the Array sort() implementation always sorts by string values unless a sort function is supplied. In other words, the default sort comparator always calls "toString" before comparing. – Pointy Aug 6 '10 at 12:47
@Pointy: ugh, that's nasty. I had to try it out before I could believe it. What were they thinking? – Michael Borgwardt Aug 6 '10 at 12:54
I don't know, but I spent about 10 minutes on the issue just the other day :-) – Pointy Aug 6 '10 at 13:50
feedback
up vote 3 down vote

This is because for any other language, I didn't find this problem where the function didn't sort the numbers correctly.

Consider your emphasis in the above sentence: you are precisely not sorting numbers. You are sorting strings! And JavaScript behaves like any other language would in this case.

If you want to consider these strings as numbers for the purpose of sorting, you have to tell the function this.

share|improve this answer
feedback
up vote 3 down vote

The function sort will sort your array in an alphabetical sort order, even if it consists of integers; that's the reason why your array is sorted like that by calling sort without a parameter.

sortOrder is a comparison function that is used to define a new sort order for the array; this function will return

  • 0, if a and b are of the same value
  • a value > 0, if a has a bigger value than b
  • a value < 0, if a has a smaller value than b

In JavaScript, "1" - "2" will return -1, which is a number, and not a string anymore; by using the comparison function sortOrder on your array consisting of numbers wrapped in strings, you're ordering the array in a numerical sort order, thus resulting in 1,5,10,25,40,100, and not in 1,10,100,25,40,5

share|improve this answer
feedback
up vote 2 down vote

You can delegate the sorting to your own sort function:

function sortnum(a,b) {
 return parseInt(a,10)-parseInt(b,10);
}
var n = ["10", "5", "40", "25", "100", "1"];
alert(n.sort(sortnum)); //=>["1", "5", "10", "25", "40", "100"]
share|improve this answer
Just a well-known tip: parseInt(a,10) can be replaced by ~~a for performance boost. – naugtur Apr 11 '11 at 18:58
@naugtur if it is so well-known tip, it won't take you much time to find a link and give it to me :)?. I want to continue reading about that – ajax333221 Feb 16 at 16:06
Here you can read all about operators: developer.mozilla.org/en/JavaScript/Reference/Operators/… And that's the best thing I know about ~~ trick: james.padolsey.com/javascript/double-bitwise-not – naugtur Feb 17 at 21:46
feedback
up vote 1 down vote

And what if your n is defined as:

var n = [10, 5, 40, 25, 100, 1];
share|improve this answer
That would not change anything, because the sort() routine always sorts by the "toString()" value of the array elements unless a specific comparator function is supplied. – Pointy Aug 6 '10 at 12:47
feedback

Your Answer

 
or
required, but never shown
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.