0

I would like to compute a numeric value for strings containing only /[a-z0-9]/i (ignore case). Later, I want to use this value for sorting rows. For this post, I am ignoring number also.

My thinking was, that I can define an alphabet like 0123456789a...z and compute a sortable value by summing up the indexes of each character found, like this (pseudo code but should work in ES6):

const alpha = 'abcdefghijklmnopqrstuvwxzy'.split('');

function easySort(myString) {
  myString = myString.toLowerCase();
  let sortableValue = 0;
  for (let i = 0; i < myString.length; i++) {
    sortableValue += alpha.indexOf(myString.charAt(i)) + 1; // to avoid 0
  }
  return sortableValue;
};

Simple example (assuming indexes a=1, b=2, ..):

let arr = ['abc', 'ab', 'abd', 'aba'];
let ordered = arr.sort((a, b) => easySort(a) - easySort(b));
// ordered now is ['ab', 'aba', 'abc', 'abd']

The question is, is this a good approach for strings from that alphabet? Are there cases when this would not work the intended way?

I am not asking for improvements of the code but rather the algorithm and whether it may behave unexpected for certain values (by that I do not mean illegal values).

4
  • Strings are already their own numeric, sortable value. Is it your intention to create a sortable value that takes up less memory? Mar 29, 2017 at 11:46
  • Yes it is, instead of the string I do intend to store the numeric value later only.
    – user654123
    Mar 29, 2017 at 11:47
  • Characters of a string are just representations of byte values from an encoding. Look at the ASCII table, you will see that each character corresponds with a single number that is orderable. If you are looking to speed up searches, then I advise reading up on various sorting algorithms and find one that is most applicable for your use case and input data.
    – maple_shaft
    Mar 29, 2017 at 11:54
  • Were you referring to hashing. Murmurhash3 is pretty unique. There is also the matter of the hashing trick which uses this and secondary hashing to compute a numeric value with limited collisions. Are you trying to sort an extremely massive set of strings or something that would be better in Spark? Mar 29, 2017 at 21:14

1 Answer 1

5

It's a bad approach because it doesn't work. This is basically a question of domain sizes.

Even with only 36 possible characters, there are vastly more possible strings than probably fit into the integer type of your choice. That means that pre-computing a sort index doesn't work; you can always get collisions between strings that should be sorted differently but that your index claims to be equal.

Therefore, strings, even from a restricted character set, are their own sorting index, and no smaller sorting index can be correct. If you don't care about exact sorting, just use a fixed-size prefix of each string instead of a complicated transformation.

2
  • While reading your answer I realized that one problem is ambiguity. That's the sort of problems I already suspected (and asked for) but couldn't quite put my finger on it ;)
    – user654123
    Mar 29, 2017 at 11:49
  • The problem is not so much ambiguity. That is a consequence of the problem. The problem is, as Kilian wrote, the size of the two domains. If you are talking about mathematical integers, then there are exactly as many integers as there are strings (both are countably infinite), so your scheme doesn't buy you anything. If we are talking about ECMAScript Numbers, then there are only finitely many of them, but infinitely many Strings, which means that you run into the Pigeonhole Principle, and there will be at least two strings which have the same number. Mar 29, 2017 at 13:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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