Sorting alphanumeric with implicit numbers

Question

I have a list of game titles that I want to sort by title and everything was going smoothly until I wanted to sort these two titles in a more "natural" way.

const titles = [
  // ...
  'Kane & Lynch 2: Dog Days',
  'Kane & Lynch: Dead Men',
  // ...
];

The problem is that I do not know how to get Kane & Lynch: Dead Men before Kane & Lynch 2: Dog Days. The Kane & Lynch: Dead Men has an implicit number 1, but sorting algorithm does not "know" about it. How is that type of sorting called? Can it be easily achieved in code (JS in particular)?

Answer 1

When you sort you get to pass a comparison function. Its logic can be as complex as you want.

Here is one which handles embedded numbers like they happen in movie titles, whether they are numbers or Roman numerals. The idea is to first replace roman numerals with numbers, and then to break into pieces specifically looking for a number.

function romanToInt(s) {
    let table = {
        I: 1,
        V: 5,
        X: 10,
        L: 50,
        C: 100,
        D: 500,
        M: 1000
    }

    for (let i = 0; i < s.length; i++) {
        if (! table[s[i]]) {
            return s;
        }
    }

    // Special case.  Usually not a number in titles. And if it was, leaving
    // it alone will compare correctly.
    if (s == 'I') {
        return s;
    }

    let result = 0;
    for (let i = 0; i < s.length; i++) {
        //if the next roman numeral is larger, then we know we have to subtract this number
        if (table[s[i]] < table[s[i+1]]) {
            result-=table[s[i]]
        }
        //otherwise, add like normal. 
        else {
            result+=table[s[i]]
        }
    }
    return "" + result

};

function normalizeRoman(s) {
    return s.split(/\b/).map(romanToInt).join("");
}

function smartCompare (s, t) {
    if (s == t) {
        return 0;
    }

    let sNorm = normalizeRoman(s);
    let tNorm = normalizeRoman(t);
    if (sNorm == tNorm) {
        if (s < t) {
            return -1;
        }
        else {
            return 1;
        }
    }

    let sArray = sNorm.match(/( \d+)|./g);
    let tArray = tNorm.match(/( \d+)|./g);

    for (let i = 0; i < sArray.length; i++) {
        if (tArray.length <= i) {
            return 1; // t comes first
        }
        else if (1 < sArray[i].length) {
            if (1 < tArray[i].length) {
                // This is " 2" vs " 3"
                // Cast to integers and do a - to compare.
                if (sArray[i] != tArray[i]) {
                    return (sArray[i] - 0) - (tArray[i] - 0);
                }
            }
            else {
                // Insert the " 1" to t, and t wins.
                return 1;
            }
        }
        else if (1 < tArray[i].length) {
            // Insert the " 1" to s, and s wins.
            return -1;
        }
        else if (sArray[i] < tArray[i]) {
            return -1; // s less at first diff
        }
        else if (tArray[i] < sArray[i]) {
            return 1; // t less at first diff
        }
    }

    // tArray must be longer.
    return -1
}

console.log([
    'Kane & Lynch 2: Dog Days',
    'Kane & Lynch: Dead Men',
    // make some up.
    'Kane & Lynch III: Zombies',
    'Kane & Lynch 10: Eternity',
    'Kane & Lynch IX: Afterlife',
].sort(smartCompare));