Where Do I Belong

In today’s installment of the Basic Algorithm Scripting series, we will return the lowest index at which a value (second argument) should be inserted into an array (first argument) once it has been sorted. The return value should be the index.

If you don’t know what the hell is still going on, no worries, we have Amsden McDono:

Amsden McDono

Amsden may not be the most handsome of all creatures. Those freckles, sleepy eyes, giant glasses, unflattering hair and grinning small teeth are not the focus of this function. The focus is what is inside that mysterious lunch box with the triangle on it.

Look at this glorious face…
The Magic Lunchbox

Inside the magic suitcase holds lets say an array of numbers…

The second argument, is a lonely cube or the number 6.

Here the array contains three numbers (could contain more or less), [4, 2, 10].

Cube #6 sits here and wonders why he wasn’t invited to the array party.

In the function, you’ll want the second parameter to be pushed into the array so that you can sort the array with all the numbers included.

So you push cube #6 into the the array and sort them using the Array sort method, everything is good right?

Well this is the result:

That’s not fair, why is #10 the first one if the array is supposed to be arranged in ascending order.

The problem here is the sort method sorts arrays lexicographically (aka “alphabetically” or in dictionary order). So if you look at the array:

Starting with the first digit, the 1 in 10 comes before 2 4 and 6.

Even in arrays containing multi-digit numbers like: [193, 125, 1, 10000], the sort method will return [ 1, 10000, 125, 193 ]. The reason is in the first digit, well all of the values have the number 1. Let’s look at the second digits on all of the numbers. The number 1 has no second digit so it therefore takes priority. The second value has 0 as the second digit and if you look at the 2 in 125 and the 9 in 193, 0 takes priority over those two numbers and so on. But what about the third digits in 125 and 193? 5 lexicographically comes after 3. Yes but since second digit in 125 comes lexicographically before the 9 in 195, it makes the entire number take priority over 193.

I probably babbled on about numbers when I should have just told you that the sort array can accept functions:

Array.sort() accepts an optional parameter in the form of a function reference. So you can pass a function to the sort method and the method will sort the array depending on the values the compare function returns.

The compare function will look at each pair of values in the array (a and b) and compares it ( a-b ). The values are returned based on the relationship between each other. Here are the three possible values. You can read more about it here:

  • Less than 0: Sort “a" to be a lower index than "b"
  • Zero: “a" and "b" should be considered equal, and no sorting performed.
  • Greater than 0: Sort “b" to be a lower index than "a".

In this small example because 2 minus 10 is -8, the return value is less than zero and therefore 2 will come before 10.

After the compare function does its sorting thing, it will now sort the array in numerical order. To get the index of the second parameter in the sorted array, you can use a javascript indexOf function.

And after all that work, the lonely cube #6 was just second value in the array.

And we conclude with a photo of Amsden and the number 2 (return value) he pulled out of his mysterious lunch box (the function).

One clap, two clap, three clap, forty?

By clapping more or less, you can signal to us which stories really stand out.