Welcome to the Treehouse Community

Want to collaborate on code errors? Have bugs you need feedback on? Looking for an extra set of eyes on your latest project? Get support with fellow developers, designers, and programmers of all backgrounds and skill levels here with the Treehouse Community! While you're at it, check out some resources Treehouse students have shared here.

Looking to learn something new?

Treehouse offers a seven day free trial for new students. Get access to thousands of hours of content and join thousands of Treehouse students and alumni in the community today.

Start your free trial

JavaScript

Posted by jonroby
jonroby
16,113 Points

Methods Part 2 Sort Function

I don't understand how the function below is able to sort the numbers in my_array (this is on Methods Part 2 video with Jim Hoskins at approximately the 4 minute mark):

var my_array = [10, 44, 32, 100, 0, 44, 3, 4];
console.log(my_array.toString());

my_array.sort(function (a,b) {
     return a - b;
});
console.log(my_array.toString());

I understand that the number that is returned will be a positive, negative, or 0, and that if the difference is positive, then a is greater -- if the difference is negative, then b is greater -- if the difference is 0, then the numbers are equal.

What I don't understand is how the sort method is able to determine the correct numerical sorting after returning the difference of each pair of numbers in the array. As I said earlier, it is obviously sufficient to determine which number is greater depending on the sign of the difference (or if the number is 0). But how does the method determine which of two numbers is greater if only pairwise comparisons are made? Does the sort work as follows:

10 - 44, 10 - 32, 10 - 100, etc.

44 - 32, 44 - 100, 44 - 0, etc.

32 - 100, 32 - 0, 32 - 44, etc.

Any help would be appreciated.

3 Answers

Jason Anello
Jason Anello
Courses Plus Student 94,610 Points

Hi Jon,

At a high level the sort method is a black box to us. We pass in an array and it sorts it for us. The compare function that you supply is a black box to the sort method. All the sort method does is pass two elements from the array into the compare function and if it gets back a negative value then it knows it must keep a before b in the final sorted array. If it's positive then it has to keep b before a and if it gets back 0 then it should treat the items as equal and it may or may not keep them in their original order. This has to do with whether the sort is stable or unstable.

This much I think you're saying you understand.

What I think you want to know about is the internal workings of the sort method. There isn't going to be any single correct answer here. The ecmascript specification doesn't require any particular sorting algorithm to be used and it also doesn't require the sort to be stable. In a stable sort, equal items will be kept in their original order. Whereas in an unstable sort, equal items might be reversed.

So each implementation is free to use whatever algorithms it wants. They may even use more than one. For instance, chrome uses a stable sort for up to ten elements and then switches to an unstable sort beyond 10 elements. This means that for an 11 element array, firefox and chrome won't necessarily produce the exact same output.

You would have to dig into the source code for the open source browsers to find out how it's actually done. You won't be able to see how IE sorts since it's closed source.

I think you are under the impression that adjacent elements are passed in to the compare function but this may be dependent on the sorting algorithm used.

Whichever algorithm is going to be used, the sort method is going to be comparing two items, not necessarily adjacent, and it needs to know whether to switch them or not. It passes those two items to the compare function and that function tells sort whether to switch them or not.

If you're really interested in this then you can start researching the various sorting algorithms out there. There are dozens but really only a few that get regularly used. The more common ones are selection, insertion, bubble, quicksort, mergesort, heapsort, and so on.

You could try implementing 1 or 2 of the simpler ones. I think that insertion and bubble sort are two of the simplest ones to start off with. Then you might better understand how the sorting is actually happening.

I hope that at least partially answers your question.

jonroby
jonroby
16,113 Points

Thank you! This is exactly what I was looking for. I began studying web design a few months ago and never studied math or computer science in college (though I did study symbolic logic). So I didn't know what was "magically" allowing the sort method to numerically order the items by pairwise comparison. So I thought either there is some routine procedure behind it, or I have missed something terribly obvious. Now I have some sense of what the answer is: a sorting algorithm (http://en.wikipedia.org/wiki/Sorting_algorithm). If time permits, I would like to study this a little bit. It looks fascinating!

Jeff Lange
Jeff Lange
8,788 Points

Jon, I was wondering about the EXACT same thing!

Jason, I've been searching through the forum for various answers to this, and yours by far makes the most sense. I was wondering why we didn't have to create if/else statements, etc, but like you said, the .sort just handle all of the sorting behind the scenes for us. THANK YOU. :)

One question (if anyone still responds to this thread...): could we write our own sorting function with if/else statements? It seems like it'd be pretty easy. Although obviously, just using the provided .sort is easier still.

Jason Anello
Jason Anello
Courses Plus Student 94,610 Points

Hi Jeff,

You're welcome.

Yes, you can certainly write your own sort function but it would be more involved than if/else statements. It might involve nested loops.

You can take a look at the sorting algorithm link that Jon left to get a general overview.

Here's the dedicated page to selection sort: http://en.wikipedia.org/wiki/Selection_sort

There you can see some example code of how it might be implemented. It uses nested for loops with a couple of if statements.

This wikibooks page shows implementations of selection sort in about a dozen languages including javascript: http://en.wikibooks.org/wiki/Algorithm_implementation/Sorting/Selection_sort

Jeff Busch
Jeff Busch
19,287 Points
Jeff Busch
Jeff Busch
19,287 Points

Hi Jon,

It must be done in the javascript sort() function. Run the following code in your browser with the console open, or replace console.log() with document.write(). Tell me what you think.

Jeff

var my_array = [10, 44, 32, 100, 0, 44, 3, 4];
console.log(my_array.toString());

my_array.sort(function (a,b) {
    console.log(a - b);
    console.log(my_array);
    return a - b;
});

console.log(my_array.toString());
jonroby
jonroby
16,113 Points
jonroby
jonroby
16,113 Points

Jeff, thanks for the reply, but the code that I wrote will in fact sort it correctly. I am trying to figure out how it is able to do this. This is what I try to elaborate on in the two paragraphs below the code.

Jeff Busch
Jeff Busch
19,287 Points

And I replied it must be done within the JavaScript sort() function. If you can find the code good for you.