JavaScript Sort and app version numbers
I recently read an intriguing blog post describing a technical challenge for an interview. The challenge is to sort, from high to low, an array of strings containing software version numbers, — e.g. 1.2, 3.43, 3.33. I decided to tackle the problem on my own as I’m in the process of preparing for interviews myself.
My initial set of sample data included version numbers that all contained the same number of characters in each partial of the version number, — i.e. all one digit partial elements.
The native JavaScript Sort method sorts by comparing successive elements of adjoining strings. The comparison is based on UTF-16 code unit values for the characters — for our purposes, this is alphanumeric order.
If the first element A < B there is no need to flip positions.
If A > B, or if no character exists at that position in B, the elements’ position’s need to be flipped.
If A = B, the next character along is compared, so on and so forth.
For strings this method sorts as expected:
For our challenge, partial numbers that stay single digits sort as expected:
arr = ["1.0", "3.3.3", "3.3", "1.6", "5" ]
arr.sort() = [“1.0”, “1.6”, “3.3”, “3.3.3”, “5”]
However, as soon as we sort a case where some version partials are longer than others, we run into the problem using the stock sort method as demonstrated below:
arr = [‘1.5’, ‘1.22’, ‘3.3’]
arr.sort() = [‘1.22’, ‘1.5’, ‘3.3’]
The reason is that the native Sort method converts all elements to strings before making comparisons which can lead to unexpected results when comparing numbers!
The 10 is sorted before the 2 because 2 > 1 from the first position. The sort method doesn’t take into account that 10 is greater than 2!
The solution is to use a custom compare function with our sort method. The sort method looks for the return values from this function to determine sort order. A custom compare function allows us to compare integers without converting them to strings. The return value of the function dictates how elements of the array are sorted.
If return > 0, flip position of elements
If return < 0, don’t flip elements
Returning 0 means the elements are equal
To compare an array of integers we can use the following simple custom sort that mathematically compares the two elements.
arr.sort(function(a, b){
return a — b
})
Now, with this in mind, we can construct a custom compare function to handle the sorting of version numbers.
The first step is to check if the two strings compared are equal, in which case we know to return 0 and are finished with those elements. Next split each version number into arrays using the ‘.’ as the split point so we can compare each of the version positions individually.
'1.10.4'.split('.') = ['1','10','4']
Now we find the version with the greatest number of version elements (this will be the length of our for loop) using Math.max() .
For the actual comparison we iterate over each partial of the versions by index. We need to convert the sections into integers using parseInt() so they can be evaluated without regard to the number of digits each value has.
Now we can check if the first or second is the larger integer. In addition, if the sections are equal, we check if a current partial is the last partial. If so we know the other partial will be greater.
Finally we use our compare function with sort and reverse the results to get a descending list:
Unsorted:
[“1.3.0.9”, “0.2.0”, “3.1.2”, “0.1.6”, “5.0.0”, “3.3.3.3”, “3.3.3.3.3”, “3.10”, “0.2.0”]
Sorted:
[“5.0.0”, “3.10”, “3.3.3.3.3”, “3.3.3.3”, “3.1.2”, “1.3.0.9”, “0.2.0”, “0.2.0”, “0.1.6”]
That’s it!
function comparePartials(a, b) {if (a === b) {
return 0;
}let splitA = a.split('.');
let splitB = b.split('.');const length = Math.max(splitA.length, splitB.length);for (let i = 0; i < length; i++) {//FLIPif (parseInt(splitA[i]) > parseInt(splitB[i]) ||
((splitA[i] === splitB[i]) && isNaN(splitB[i + 1]))) {
return 1;
}//DONT FLIPif (parseInt(splitA[i]) < parseInt(splitB[i]) ||
((splitA[i] === splitB[i]) && isNaN(splitA[i + 1]))) {
return -1;
}
}
}// Performing the actual sort
function sortVersions(arr) {
return arr.sort(comparePartials).reverse()
}
