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
Adam Posey
Courses Plus Student 7,823 PointsSort Numerically in Arrays
I've watched the video and passed the code challenge but I'm really interested in why
javascript
x.sort(function(a,b) {
return a-b;
});
functions as it does to return the appropriate result. It seems the "SortFunction" is only concerned with positivity, negativity, or equality in the return. Many examples online create code which returns 0, -1, or 1 as a result of the comparison between a and b. For the purposes of SortFunction 0,-8,3 are equivalent to 0,-1,1.
However, I don't understand how it is that a and b are actually called. It seems like it could become computationally expensive for the function to call every possible set of numbers and compare them individually and return the result.
I suppose that makes it a testable hypothesis because there should be an increase in time-to-return as the set increases in size. If this is the case and each possible pairing is truly compared then what implications does this have for using the SortFunction numerically in our code when producing web applications? Is it only practical/functional on small sets of information? Would an array large enough to slow this function be terrible practice anyway and therefore practically result in the law that any array too big to sort is an array too big to use?
2 Answers
Laurence Stokes
6,109 PointsThere are many sorting algorithms that you can use. The most intuitive sort is bubblesort, which is easy to implement, just horribly inefficient at sorting large values. It has an average time complexity of 0(n^2), meaning that for an array of size 10, you'd have to perform 100 calculations to sort it. Mergesort, developed by Von Neumann, has a time complexity (in all cases, best/worst/average) of O(n log n), meaning for an array of size 10, it takes only 23 comparisons. Mergesort does eventually have to perform a comparison like the one in the x.sort(function(a,b) where it compares which element is the biggest of the two (which is done by subtracting one from the other. A positive result would indicate a is bigger, negative b is bigger and equal that they're equal). There are tons of sites that compare and contrast the advantages and time complexities of different sorting algorithms and a quick google should bring them up!
To make it more clear on the issue of time complexity, for an array of 1 million indices, bubble sort would take 1million^2 (1 trillion using American nomenclature) calculations whereas mergesort would take just 1.4 million. For brevity, assume we can perform 1 million processes a second, bubble sort would take 1 million seconds, or 11.57 days, whereas mergesort would take only 1.4 seconds. As arrays of size 1 million are not unheard of, this kinda time saving stuff really becomes necessary. :)
As for your question, I don't think we could ever create an array that we couldn't sort, as we can make sorting a logarithmic complexity.
Laurence Stokes
6,109 PointsYou also have to take into consideration space (RAM), and special cases (i.e. if a list is nearly sorted).
http://www.cprogramming.com/tutorial/computersciencetheory/sortcomp.html