Developapa

Excel column sort

May 29, 2020

In this quick tutorial I’m going to explain how to build a JavaScript function that can generate Excel column sort values.
I will build this function recursive, if you have concerns regarding performance, you might want to checkout my Conclusion below.

If you are just here for the code itself and don’t bother how it actually works, just go ahead and copy paste it. (you can also find it in my Gist)

function numberToLetters(index) {
    const charLimit = 26;
    if (index > charLimit) {
        if (index % charLimit === 0) {
            return '' 
                + numberToLetters((index / charLimit) - 1) 
                + numberToLetters(charLimit);
        } else {
            return '' 
                + numberToLetters(Math.trunc(index / charLimit)) 
                + numberToLetters(index % charLimit);
        }
    } else {
        const a = 'A'.charCodeAt(0);

        return String.fromCharCode(a + index - 1);
    }
}

If you use TypeScript you can also use this version

function numberToLetters(index: number): string {
    const charLimit: number = 26;
    if (index > charLimit) {
        if (index % charLimit === 0) {
            return `${numberToLetters((index / charLimit) - 1)}${numberToLetters(charLimit)}`;
        } else {
            return `${numberToLetters(Math.trunc(index / charLimit))}${numberToLetters(index % charLimit)}`;
        }
    } else {
        const a: number = 'A'.charCodeAt(0);

        return String.fromCharCode(a + index - 1);
    }
}

Implementation

Get a character for number 26 or smaller

Let’s start of with how to get the letters from the alphabet. A lot of solutions I saw online use some Array that contains all 26 letters, but this is actually not needed. JavaScript has a String.fromCharCode(NUMBER) (mdn documentation) function that returns the string value of the UTF-16 character that represents the NUMBER value (What is unicode).
There are tables with an overview what number represents which value. char code table

For us is just important that there is a sequence in there that contains all letters from A to Z in the right order (from 65 to 91).
I’m not a big fan of defining unneeded hard coded limits (in that case start value of 65) and therefore we can get the starting value with

const a = 'A'.charCodeAt(0);

charCodeAt(number) is the inverse of our previous method. Now we have the variable a that holds the starting value of 65.

We want to always get the character at a certain index of the alphabet, e.g.

  • param 1 → A
  • param 2 → B
  • param 26 → Z
String.fromCharCode(a + index - 1)

We have to subtract 1 from the index since we start counting at 0 because start variable a already represents the character A.

So far, so good.

Numbers greater than 26

Our basic construct will be an if-else to decide whether the value is greater than 26, because in this scenario we have to split the number and extract how often 26 fits into it and shift the number one position (28 actually has 2 digits, 26 resulting in the first digit A and the rest of 2 results into B → AB).
If the value is lower than 26 we can get the value at the given index from the step above. Currently our code looks like this

function numberToLetters(index) {
    const charLimit = 26;
    if (index > charLimit) {
      
    } else {
        const a = 'A'.charCodeAt(0);
    
        return String.fromCharCode(a + index - 1);
    }
}

The next part might actually be a little bit confusing at first. We need to check whether our given number can be divided by 26 without a rest. Because if there is no rest we are 1 step before ‘the jump’. For example: From 27 on all values start with an A followed up with the letter that represents the rest. 52 is actually the last number before the jump to the next digit. 52 is AZ while 53 is AAA.
In JavaScript you can check this with the modulo (%) operator

> 52 % 26
< 0
> 53 % 26
< 1

Added to our code it now looks something like this

const charLimit = 26;
if (index > charLimit) {
    if (index % charLimit === 0) {
        // special case if there is no rest
    } else {
        // regular case
    }
} else {
    const a = 'A'.charCodeAt(0);

    return String.fromCharCode(a + index - 1);
}

Recursion

We will build our function recursive.

In programming terms a recursive function can be defined as a routine that calls itself directly or indirectly (geeksforgeeks.org)

In our case this is pretty handy, because we can just split up our number into smaller parts and call our own function with each part and then simply combine the result.

Let’s start with our regular case first.

If our number is greater than 26, we will always split the number up into at least two numbers. One represents how often 26 fits into our given number and the other one the rest.
With Math.trunc(index / charLimit) we get the first one (Math.trunc removes all potential decimal values).
Math.trunc(value / 26):

  • value = 52 → 2
  • value = 53 → 2
  • value = 78 → 3
  • value = 79 → 3

Like mentionend earlier with this number we now want to call our function numberToLetters itself to get the letter for our first digit.

We already learned that with modulo we can get the rest (index % charLimit). Same principle applies for this case - a call to numberToLetters will give us our second digit.

Put together our regular case looks like this

return '' 
  + numberToLetters(Math.trunc(index / charLimit)) 
  + numberToLetters(index % charLimit);

Before we go on to our last special case, let’s check our previous lines in theory with 2 examples.
numberToLetters(76):
76 split up is: 2 * 26 + 24.
Calling numberToLetters(2) results in a B and numberToLetters(24) in a X. Our result is BX

numberToLetters(1991): 1991 split up is: 76 * 26 + 15.
Well, now we face the problem that our first number itself is actually bigger than 26, so we have to split it up again. In this case we already know from our previous example that numberToLetters(76) is BX and numberToLetters(15) is O.
numberToLetters(1991) results in a total of BXO

With everything we learned so far our special case can be implemented like this

return '' 
    + numberToLetters((index / charLimit) - 1) 
    + numberToLetters(charLimit);

We basically manually jump one digit back. 52 / 26 results in 2 and would return us B. But actually we need an A. So we just subtract 1 from it. Since we now there are no leftovers (from our previous modulo check index % charLimit === 0) the last value is just the last possible letter of the alphabet → Z.
With that in place numberToLetters(52) correctly returns AZ.

If we put everything together we get our fully working function

function numberToLetters(index) {
    const charLimit = 26;
    if (index > charLimit) {
        if (index % charLimit === 0) {
            return '' 
                + numberToLetters((index / charLimit) - 1) 
                + numberToLetters(charLimit);
        } else {
            return '' 
                + numberToLetters(Math.trunc(index / charLimit)) 
                + numberToLetters(index % charLimit);
        }
    } else {
        const a = 'A'.charCodeAt(0);

        return String.fromCharCode(a + index - 1);
    }
}

Conclusion

This should just be a little guide and can be an easy example on how to explain and learn recursion. I know that due to the recursion this is not the fastest solution out there, but unless you are generating all sort values up until like 1.000.000 and beyond you are totally fine.
Here is a little test script time-test.js

const LIMIT = 1000000;
console.time('performanceTest');
const sortValues = [];
for (let i = 0; i < LIMIT; i++) {
  sortValues.push(numberToLetters(i));
}
console.timeEnd('performanceTest');
console.log(sortValues.length);

And calling $ node time-test.js resulted in performanceTest: 256.638ms (the ’.’ in this case is the decimal separator). So generating the first one million sort values only takes 250ms. But if you test higher limits, e.g. 10mio (takes ~5-6 seconds), you quickly see that recursive functions don’t scale linear ;)
In my case I needed values up until 1.000 and that takes not even a millisecond, and I think this is totally fine.

Personal Blog written by Nicolas Gehlert, software developer from Freiburg im Breisgau. Developer & Papa. Github | Twitter

Add a comment

Comments

There are no comments available for this blog post yet

© 2024, Nicolas Gehlert