5
\$\begingroup\$

This code sorts string that may contain numbers in natural order, that's it, "item 2" comes before than "item 10". It currently ignores case. I plan to implement options to handle case sensitivity and descending order.

For me it's fast enough, faster than other implementations I've seen using regexes. Apart from the first lines, it's JavaScript.

I made it returning the actual sorting function so we can cache its config object.

I'd like to know if it have any issues regarding Unicode, code style, etc. I plan to handle descending order like this, codified into a helper function.

return 0 - result;

For case sensitivity, I'd strip toUpperCase().

"use strict";

interface NaturalKeyFunc {
    (obj: any): any;
}

interface NaturalSortConfig {
    keyFunc?: NaturalKeyFunc;
    //desc?: boolean;
    //caseInsensitive?: boolean;
}

function naturalSort(config?: NaturalSortConfig) {

    return function(a, b) {

        if (typeof a === "number" && typeof b === "number")
            return a - b;

        if (a === null || b === null)
            return NaN;
        if (a === undefined || b === undefined)
            return NaN;
        if (Array.isArray(a) || Array.isArray(b))
            return NaN;

        if (Object.prototype.toString.call(a) === "[object Object]" || typeof Object.prototype.toString.call(b) === "[object Object]") {
            if (!config && !config.keyFunc)
                return NaN;
            if (typeof a === "object")
                a = config.keyFunc(a);
            if (typeof b === "object")
                b = config.keyFunc(b);
        }

        if (typeof a !== "string" || typeof b !== "string")
            return a - b;

        if (a.length === 0 || b.length === 0)
            return a.length - b.length;

        var s1: string = a,
            s2: string = b,
            indexA = 0, indexB = 0,
            numberA, numberB,
            charA, charB,
            difference;

        do {
            numberA = 0;
            while (indexA < s1.length) {
                charA = s1[indexA];
                indexA++;
                if (!(charA >= "0" && charA <= "9")) break;

                numberA = numberA * 10 + parseInt(charA);
            }

            numberB = 0;
            while (indexB < s2.length) {
                charB = s2[indexB];
                indexB++;
                if (!(charB >= "0" && charB <= "9")) break;

                numberB = numberB * 10 + parseInt(charB);
            }

            if (charA === " " && charB === " ") {
                while (indexA < s1.length && s1[indexA] === " ") {
                    indexA++;
                }
                while (indexB < s2.length && s2[indexB] === " ") {
                    indexB++;
                }
            }

            difference = numberA - numberB;
            if (difference !== 0) return difference;
            if (charA !== charB) {
                if (charA === ".") return -1;
                if (charB === ".") return 1;
                return charA.toUpperCase().charCodeAt(0) - charB.toUpperCase().charCodeAt(0);
            }
        } while (indexA < s1.length && indexB < s2.length);

        return (indexB - s2.length) - (indexA - s1.length);
    }
}

Some tests:

let natu = naturalSort();

it("can sort numbers inside strings", function () {
    expect(natu("a1", "a2")).toBeLessThan(0);
    expect(natu("1 item", "1 item")).toEqual(0);
    expect(natu("item 1", "item 1")).toEqual(0);
    expect(natu("item 1", "item 2")).toBeLessThan(0);
    expect(natu("item 1", "item 10")).toBeLessThan(0);
    expect(natu("item 2", "item 10")).toBeLessThan(0);
    expect(natu("item 1 item a", "item 1 item a")).toEqual(0);
    expect(natu("item 1 item 1", "item 1 item 10")).toBeLessThan(0);
    expect(natu("item 01", "item 1")).toEqual(0);
});
\$\endgroup\$
6
  • \$\begingroup\$ Some test cases: [1] Negative numbers if "Natural" refers to the order rather than the type of number [2] Hexadecimal and Octal and Binary numbers under the "etc" in "anything....etc." if withing the scope of "etc." [3] Unicode ordering of letters should probably be based on the locale in which the software is run and that's a big can of worms and a vast vast number of tests. \$\endgroup\$ Feb 4, 2015 at 3:26
  • \$\begingroup\$ You may want to have a look at some of the ideas used in this one. The second version there actually probably should be studied for a while for some really great tips on optimizing JavaScript. \$\endgroup\$
    – Eric Blade
    Feb 4, 2015 at 8:09
  • \$\begingroup\$ I would like to treat - as a separator instead of a negative number. For instance Red Hot Chili Peppers-10. If negative, it would turn into descending order. As for Unicode, as guess I don't really know much of it... \$\endgroup\$ Feb 4, 2015 at 10:36
  • \$\begingroup\$ Ignoring negative numbers is not handling them. Suppose I am using the algorithm and I have already labeled something "item 0" and I want to order something before it. Robust software will catch sequences that look like negative numbers and warn me of possible unexpected behavior, or fail, or do what I expect. Fast bad data is often worse than slow correct data. \$\endgroup\$ Feb 4, 2015 at 12:13
  • \$\begingroup\$ What if you want to insert something after "item 0" and you already have "item 1", "item 2", "item 3", "item 4", "item 5", "item 6"...up to a million items if you wish? What trick would you employ? A classification system based on these scheme would just fall short. Besides, "-" comes before any digits, so "item -1" would come just before "item 0". plnkr.co/edit/a9lmShDDAFNJnXmFQ8mm?p=catalogue But who would think in ASCII ordering, besides programmers? Thank you for your considerations. \$\endgroup\$ Feb 4, 2015 at 12:48

1 Answer 1

6
\$\begingroup\$

Dead code

interface NaturalSortConfig {
    keyFunc?: NaturalKeyFunc;
    //desc?: boolean;
    //caseInsensitive?: boolean;
}

Dead code does nothing, except take up screen space, and confuse people who don't know why it was written and removed in the first place.

Braces

This is a bit of a holy-war. However, at least one bug (the Apple SSL bug) was caused by missing braces. Personally, I use them:

if (typeof a === "number" && typeof b === "number") {
    return a - b;
}

Instead of:

if (typeof a === "number" && typeof b === "number")
    return a - b;

Functions

You may want to consider splitting this into more methods. One possible method might be to move the code to determine whether to early-return into its own function:

function IsValidData (o) {
    return o === null || o === undefined || Array.isArray(o);
}

Most of the code in naturalSort() is duplicated - more functions would really help here.

Early exit

As mentioned in the comments in the previous (deleted) answer, you can early-return as soon as you know which value is sorted higher. For example, sorting "aa" against "bb" should be able to return after checking the first character of each, while "aaa" vs. "aba" should be able return after checking the second, and so on.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.