Sort alphanumeric strings - Letters first

Question

var List = ["F", "60", "59", "6", "7", "7'", "60'", "60a", "c1", "A", "5", "a1", "6.2", "A'", "B", "A1"];

var sortedListe = List.sort(function (a, b) {
  var collator = new Intl.Collator('en', { numeric: true, sensitivity: "base" });
  return collator.compare(a, b);
});

console.log(sortedListe);

What I get: ["5", "6", "6.2", "7", "7'", "59", "60", "60'", "60a", "A", "A'", "a1", "A1", "B", "c1", "F"]

https://jsfiddle.net/5coraw0z/

PRO: 6.2 comes before 7; 7' is also in the right place; c1 is between B and F. CONTRA: Strings beginning with a letter are at the end of the list.

My expected result: ["A", "A'", "a1", "A1", "B", "c1", "F", "5", "6", "6.2", "7", "7'", "59", "60", "60'", "60a"]

Answer 1

If you need non-standard sorting rules, it's often easier to sort each part of the array separately rather than inventing a convoluted sorting callback:

function partition(ary, fn) {
    let res = [[], []]
    for (let x of ary)
        res[fn(x) ? 1 : 0].push(x)
    return res
}

let List = ["F", "60", "59", "6", "7", "7'", "60'", "60a", "c1", "A", "5", "a1", "6.2", "A'", "B", "A1"];

let collator = new Intl.Collator('en', { numeric: true, sensitivity: "base" });

let sortedListe = [].concat(
  ...partition(List, x => !isNaN(x[0]))
    .map(a => a.sort(collator.compare)))

console.log(...sortedListe);

Answer 2

With this kind of data we could avoid the collator. The logic is to sort the items char by char with fetching as much as possible digit chars. At first sight it could look complicated, but that's just char by char comparison with alpha/numeric/undefined cases.

The goal was speed, to avoid any intermediate arrays like in the gog's soluiton.

There's also an important difference that the gog's solution splits everything into 2 alpha and numeric strings to compare. While my solution accept any number of alpha/numeric strings combined.

const list = ["F", "60", "59", "6", "7", "7'", "60a", "60'", "c1", "A", "5", "a1", "6.2", "A'", "B", "A1"];

// fetch as much as possible digits from a position in a string plus adjust the position
const gainNum = (str, idx) => {
  let num = '';
  for(;idx < str.length; idx++){
    const c = str[idx];
    if( c < '0' || c > '9' ) break;
    num += c;
  }
  return {num, idx};
}

function sort(aa, bb, ai = 0, bi = 0) {

  // compare numbers
  let anum, bnum;
  ({num: anum, idx: ai} = gainNum(aa, ai));
  ({num: bnum, idx: bi} = gainNum(bb, bi));

  if(anum) return bnum ? anum - bnum || sort(aa, bb, ai, bi) : 1; else if(bnum) return -1;

  // compare string lengths
  if(ai===aa.length) return  bi < bb.length ? -1 : 0; else if(bi === bb.length) return 1;

  // compare alpha chars
  let a = aa[ai].toLowerCase();
  let b = bb[bi].toLowerCase();
  return a === b ? sort(aa, bb, ai + 1, bi + 1) : a > b ? 1 : -1;
}

console.log('expected:', ...["A", "A'", "a1", "A1", "B", "c1", "F", "5", "6", "6.2", "7", "7'", "59", "60", "60'", "60a"]);

console.log('sorted  :', ...list.slice().sort(sort));

` Chrome/118
------------------------------------------------------
Alexander   1.00x  |  x100000  150  156  182  188  190
gog         4.40x  |  x100000  660  665  666  670  672
------------------------------------------------------
https://github.com/silentmantra/benchmark `

const list = ["F", "60", "59", "6", "7", "7'", "60a", "60'", "c1", "A", "5", "a1", "6.2", "A'", "B", "A1"];

// @benchmark gog

function partition(ary, fn) {
    let res = [[], []]
    for (let x of ary)
        res[fn(x) ? 1 : 0].push(x)
    return res
}

let collator = new Intl.Collator('en', { numeric: true, sensitivity: "base" });

[].concat(
  ...partition(list, x => !isNaN(x[0]))
    .map(a => a.sort(collator.compare)))

// @benchmark Alexander

// fetch as much as possible digits from a position in a string plus adjust the position
const gainNum = (str, idx) => {
  let num = '';
  for(;idx < str.length; idx++){
    const c = str[idx];
    if( c < '0' || c > '9' ) break;
    num += c;
  }
  return {num, idx};
}

function sort(aa, bb, ai = 0, bi = 0) {

  // compare numbers
  let anum, bnum;
  ({num: anum, idx: ai} = gainNum(aa, ai));
  ({num: bnum, idx: bi} = gainNum(bb, bi));

  if(anum) return bnum ? anum - bnum || sort(aa, bb, ai, bi) : 1; else if(bnum) return -1;

  // compare string lengths
  if(ai===aa.length) return  bi < bb.length ? -1 : 0; else if(bi === bb.length) return 1;

  // compare alpha chars
  let a = aa[ai].toLowerCase();
  let b = bb[bi].toLowerCase();
  return a === b ? sort(aa, bb, ai + 1, bi + 1) : a > b ? 1 : -1;
}


list.slice().sort(sort);

/*@end*/eval(atob('e2xldCBlPWRvY3VtZW50LmJvZHkucXVlcnlTZWxlY3Rvcigic2NyaXB0Iik7aWYoIWUubWF0Y2hlcygiW2JlbmNobWFya10iKSl7bGV0IHQ9ZG9jdW1lbnQuY3JlYXRlRWxlbWVudCgic2NyaXB0Iik7dC5zcmM9Imh0dHBzOi8vY2RuLmpzZGVsaXZyLm5ldC9naC9zaWxlbnRtYW50cmEvYmVuY2htYXJrL2xvYWRlci5qcyIsdC5kZWZlcj0hMCxkb2N1bWVudC5oZWFkLmFwcGVuZENoaWxkKHQpfX0='));

Answer 3

A representation function repr and a TrueSet implementing representation-based equivalences among objects (see the @ut8pia/classifier library) can immediatly provide the expected order.

After posing:

const 
    data = ["F", "60", "59", "6", "7", "7'", "60'", "60a", "c1", "A", ...],
    expected = ["A", "A'", "a1", "A1", "B", "c1", "F", "5", "6", "6.2", ...],
    collator = new Intl.Collator('en', { 
        numeric: true, 
        sensitivity: 'case', 
        caseFirst: 'lower'
    })

the items are added to a TrueSet:

const
    repr = item => [Number.parseInt(item[0] + 1)? 1: 0],
    set = TrueSet.of(repr, ORDER.ASCENDING, collator.compare.bind(collator))
        .letAll(data);

assert.deepEqual(Array.from(set), Array.from(new Set(expected)))

and, voilà, the expected order is achieved.

The repr function categorizes items, assigning 1 to those starting with a digit and 0 to others. The first comparator ORDER.ASCENDING in the TrueSet creator sorts these classes, while within each class, the order is determined by the second comparator, collator.compare.

It's important to note that the TrueSet doesn't iterate over duplicate items. However, it retains the count of occurrences for each item, accessible via the method n(item)

const
    got = Array.from(set)
        .map(item => new Array(set.n(item)).fill(item))
            .flat();

assert.deepEqual(got, expected)