Now I know this will be a stupid question to many, but I cannot understand this logic. So, here is the problem in short:
var points = [40, 100, 1, 5, 25, 10];
points.sort(function(a, b){return a-b});
Now suppose, values 40 and 100 are pared, so the pare function returns a negative value, i.e -60. So, 40 is placed before 100. Understood.
Now, I do this:
var points = [40, 100, 1, 5, 25, 10];
points.sort(function(a, b){return b-a});
Again, if 100 and 40 are pared, the pare function returns a positive value, i.e 60. Now, shouldn't it place 100 after 40 because of that positive returned value? But it doesn't, and I am not getting that.
I just want to know what is happening here.
Now I know this will be a stupid question to many, but I cannot understand this logic. So, here is the problem in short:
var points = [40, 100, 1, 5, 25, 10];
points.sort(function(a, b){return a-b});
Now suppose, values 40 and 100 are pared, so the pare function returns a negative value, i.e -60. So, 40 is placed before 100. Understood.
Now, I do this:
var points = [40, 100, 1, 5, 25, 10];
points.sort(function(a, b){return b-a});
Again, if 100 and 40 are pared, the pare function returns a positive value, i.e 60. Now, shouldn't it place 100 after 40 because of that positive returned value? But it doesn't, and I am not getting that.
I just want to know what is happening here.
Share Improve this question asked Dec 4, 2015 at 16:24 codetalkercodetalker 5861 gold badge6 silver badges21 bronze badges 2-
To pare numbers:
function(a, b){ if (b > a) return -1; if (b < a) return 1; return 0; }
. – Andy Commented Dec 4, 2015 at 16:32 - Of course it will be simple reverse. – user5548116 Commented Dec 4, 2015 at 16:38
5 Answers
Reset to default 3Your pare functions are exactly correct - you are using subtraction, which is very fast pared to branching and is in fact what a typical processor does when paring two integer values. Essentially:
- If your pare function returns 0, it doesn't matter what order the two should be in.
- If your pare function returns less than 0 (it doesn't matter how far), the first argument should go before the second argument.
- If your pare function returns greater than 0 (again, it doesn't matter how far), the second argument should go before the first argument.
This last bit was where you got confused in your logic - in your head, you flipped both the order of the values and changed "before" to "after", which brings the statement right back to the first one again. :) Remember - the names of the parameters or whatever happens to them in the function does not matter - it is simply the order they e in the function arguments and the corresponding result returns.
From the Mozilla documentation:
If pareFunction is supplied, the array elements are sorted according to the return value of the pare function. If a and b are two elements being pared, then:
If pareFunction(a, b) is less than 0, sort a to a lower index than b, i.e. a es first. If pareFunction(a, b) returns 0, leave a and b unchanged with respect to each other, but sorted with respect to all different elements. Note: the ECMAscript standard does not guarantee this behaviour, and thus not all browsers (e.g. Mozilla versions dating back to at least 2003) respect this.
If pareFunction(a, b) is greater than 0, sort b to a lower index than a.
pareFunction(a, b) must always return the same value when given a specific pair of elements a and b as its two arguments. If inconsistent results are returned then the sort order is undefined.
Imagine that your Array has only 2 items: 100
and 60
. What happens is that when 100
is pared with 60
the function returns 40
, which is a positive value. When 60
is pared with 100
the function returns -40
which is a negative value... That's how sort
knows where to put each element.
Perhaps you are getting confused because you don't understand how sorting algorithms work internally, if that's the case have a look at these 2:
- Heapsort
- Mergesort
Be aware that your parison function is not guaranteed to be called only once per entry of your array, and it is certainly not done in linear time (O(n)
) but depending on the algorithm, it is at best O(n log n)
.
What I mean is that, 40 will not only be pared to 100, but also to 1 and 5 etc. so you (human) can't really predict at sight that 100 - 40
will sort it in the specific way you expect it to just after the parison (several parisons occur per value), because there are several steps that determine the final index of each value.
According to definition of sort() method is to sort the elements of an array in place and returns the array. The default sort is according to string Unicode code points.
Compare pudocode looks like:
function pare(a, b) {
if (a is less than b by some ordering criterion) {
return -1;
}
if (a is greater than b by the ordering criterion) {
return 1;
}
// a must be equal to b
return 0;
}
To pare number:
function pare(a, b) {
return a - b;
}
Functionally, (ignoring the fact that integer overflow occurs for the maximum values), what happens for ascending order (a-b
), is equivalent to the following.
var ascSort = function(a, b) {
if (a > b) {
return 1;
} else if (a < b) {
return -1;
} else {
return 0;
}
}
And descending order, just negate the return values to flip the ordering
var descSort = function(a, b) {
if (a > b) {
return -1;
} else if (a < b) {
return 1;
} else {
return 0;
}
}
And so you can now do
[40, 100, 1, 5, 25, 10].sort(ascSort); // [1, 5, 10, 25, 40, 100]
[40, 100, 1, 5, 25, 10].sort(descSort); // [100, 40, 25, 10, 1]