Archives For sort order

At work recently I’ve been hacking out some front-end Javascript focused on DOM manipulation. I wasn’t that pleased with how intuitive the syntax felt to me or my ability to implement event logic. While I was fresh off lots of Node.js, some CSS work, a few copy-paste extensions of existing coffeescript, as well as implementing a mobile-friendly .js tooltip plug-in, I thought it would go easier.

So I hit the books this weekend, revisiting both:

 

Something caught my brain in Chapter 3 of Secrets of Javascript Ninja. Here the authors stress the importance of functions as “first class citizens” in the language. While comparing the brevity of a sort descending function between Java and Javascript, the authors use the following example:

var values = [ 213, 16, 2058, 54, 10, 1965, 57, 9];

values.sort(function(value1, value2) {

return value2 - value1;

});

While I understood that the function was taking the difference between values, I couldn’t see how many times it was running or what it was doing with the deltas between the two numbers.

So I took to my old friend Microsoft Excel to try and “see” what was happening here.

Screen Shot 2014-03-09 at 2.55.39 PM

Note: The above screenshot is gibberish. The only value it provides is to show what does not work.

After about an hour of feeling like a numerologist, I remembered a YouTube video I’d seen months prior and enjoyed (but didn’t fully understand).

I watched it again with a new perspective, fascinated all over again. And while it brought some clarity, it also brought a sense of staring up a frozen waterfall I’d need to climb to unlock the next layer of the onion.

Being the lazy SOB I am, I went to a friend who lets me ask him inane computer science questions. And because I know he’s horrible at e-mail, I hit him up on Facebook. I could see he was online with his mobile.

Here’s our exchange:

Me:  Trying to mathematically understand or prove… values.sort(function(value 1, value2){ return value2 - value1; }); as it relates to ordering a random array. I tried to solve it using Excel and patterns were deceptive. Which lead me to revisit this video

Me:  So I don’t understand the function, but I feel I understand there’s multiple ways to do it mathematically and Excel is not the right tool to prove this math?

Friend:  This is sorting descending right?

Me:  right!

Friend:  Okay so if value 2 is bigger then the result is a positive number which means reorder.

Friend:  But if it’s negative then do not reorder.

Friend:  0 means they are the same so nothing will happen…

Friend:  So only sign matters.

Me:  how many times does this need to run?

Friend:  Depends on the algo

Friend:  For a naive sort it’s n squared. Merge sort is nlogn

Me:  what’s under the hood for Javascript?

Friend:  Could be quick sort…

Friend:  That’s also nlogn.  I think

Friend:  It’s easy to derive sorting order of algos, all you have to know is what happens in there and then you can use methods like plug and chug to get to the order

Me:   when do you choose a different sorting strategy?

Friend:  Speed.  Some can be distributed.

Friend:  So some interview questions at google are like how would you sort 4 million integers.

Friend:   Then they ask what if you had 100 machines.

Me:   love it

Friend:   But for the most part you can use library functions and not worry about it… They are usually optimized for generic use. Keyword is generic here.

Me:   thx man

Friend:   Np, I love this stuff!

WHAT’S THE POINT?

Maybe this has given you some fresh perspective on sorting and/or Javascript. If not, well – try this:

Learning can’t me measured in big or small increments. Progress is on a person-specific continuum and all nodes on that continuum must be crossed. If you’re having a good time, keep going.

Also be thankful for other, smarter devs who are willing to throw you up to the top of a frozen waterfall from time to time. If you get a chance to help someone on their journey, do it.