JavaScript sort with numbers

Question

The following program (taken from a tutorial) prints the numbers in an array in order from lowest to highest. In this case, the result will be 2,4,5,13,31

My question relates to the paramaters "a" and "b" for the function compareNumbers. When the function is called in numArray.sort(compareNumbers) what numbers will be the parameters a and b for the function. Does it just move along the array. For example, start with a=13 and b=2? After that, does the function run again comparing a=2 and b=31? or would it next compare a=31 and b=4?

Can someone please explain how that part works and also how it manages to sort them from lowest to highest? I don`t see how the function manages to do the necessary calculations on the numbers in the array.

function compareNumbers(a,b) {
  return a - b;
}

var numArray = [13,2,31,4,5];
alert(numArray.sort(compareNumbers));

templatetypedef · Accepted Answer · 2011-03-02 01:37:06Z

The particular pairs that get passed in depend on the sorting algorithm being used. As the algorithm tries to go about sorting the range, it needs to be able to compare pairs of values to determine their ordering. Whenever this happens, it will call your function to get that comparison.

Because of this, without inside knowledge about how the sorting algorithm works, you cannot predict what pairs will get compared. The choice of algorithm will directly determine what elements get compared and in what order.

Interestingly, though, you can actually use the comparison function to visualize how the sort works or to reverse-engineer the sorting algorithm! The website sortviz.org has many visualizations of sorting algorithms generated by passing custom comparators into sorting functions that track the positions of each element. If you take a look, you can see how differently each algorithm moves its elements around.

Even more interestingly, you can use comparison functions as offensive weapons! Some sorting algorithms, namely quicksort, have particular inputs that can cause them to run much more slowly than usual. In "A Killer Adversary for Quicksort," the author details how to use a custom comparator to deliberate construct a bad input for a sorting algorithm.

Hope this helps!

Gareth McCaughan · Accepted Answer · 2011-03-02 01:36:09Z

2

The two parameters will be elements of your array. The system will compare enough pairs to be able to sort them correctly. Nothing else is guaranteed.

There are lots of things the sort method could be doing under the hood; see, e.g., http://en.wikipedia.org/wiki/Sorting_algorithm for some of them. Most Javascript implementations probably use some variant of either quicksort or mergesort.

(Here are super-brief descriptions of those. Quicksort is: pick an element in the array, rearrange the array to put everything smaller than that in front of everything larger, then sort the "smaller" and "larger" bits. Mergesort is: sort the first half of the array, sort the second half of the array, and then merge the two sorted halves. In both cases you need to sort smaller arrays, which you do with the same algorithm until you get to arrays so small that sorting them is trivial. In both cases, good practical implementations do all sorts of clever things I haven't mentioned.)

answered Mar 2, 2011 at 1:36

Gareth McCaughan

20k1 gold badge43 silver badges64 bronze badges

2 Comments

mjmitche Over a year ago

so the "sort" method determines what elements get passed into the compareNumbers function?

Gareth McCaughan Over a year ago

Yup. By the way, do check out the "killer adversary" paper that templatetypedef mentioned, though you might find it heavy going.

Alexei Levenkov · Accepted Answer · 2011-03-02 01:32:32Z

0

It will be called for all pairs of a,b that sorting algorithm need to get all array sorted. Check out http://en.wikipedia.org/wiki/Sorting_algorithm for brief list of sorting algorithms.

answered Mar 2, 2011 at 1:32

Alexei Levenkov

101k15 gold badges138 silver badges189 bronze badges

3 Comments

mjmitche Over a year ago

but how does it choose a pair of numbers to compare from an array with 5 numbers in it? Do you know the steps it takes to process the array. Does it start comparing 13 and 2 in this case? and then 2 and 31? or does it magically compare all the numbers in the array at the same time?

Mike Samuel Over a year ago

the comparator will not be called with all pairs. That would require O(n**2) calls but any decent sorting algorithm will do O(n*log(n)) calls in the average case.

Alexei Levenkov Over a year ago

Feel free to suggest edits to the first sentece... I'll gladly change it.

timrwood · Accepted Answer · 2011-03-02 02:09:02Z

When you pass a function to Array.sort(), it expects two parameters and returns a numerical value.

If you return a negative value, the first parameter will be placed before the second parameter in the array.

If you return a positive value, the first parameter will be placed after the second parameter in the array.

If you return 0, they will stay in their current position.

By doing return a - b;, you are returning a negative number if a is less than b (2 - 13 = -11), a positive number if b is less than a (13 - 2 = 11), and zero if they are even (13 - 13 = 0).

As far as which numbers are compared in what order, I believe that is up to the javascript engine to determine.

Check out the documentation on javascript array sorting at the MDC Doc Center for more detailed information. https://developer.mozilla.org/en/JavaScript/Reference/Global_Objects/Array/sort

(BTW, I always check the MDC Doc Center for any questions about how javascript works, they have the best information on the language AFAIK.)

Collectives™ on Stack Overflow

JavaScript sort with numbers

4 Answers 4

Comments

2 Comments

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

2 Comments

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related