JavaScript: Algorithm for sorting based on an predefined order of Regexes

Question

I want to sort an array of clothing sizes based on an predefined order of regular expressions.

The expressions array looks like this:

const sizeOrder = [
  /One Size/,
  /[X/S]+S/i,
  /^S$/i,
  /^M$/i,
  /^L$/i,
  /[X]+L/i,
  /[4-9]XL/i,
  /[0-9,]+/,
];

What would be a neat and efficient way to sort an array, that would for example look like this:

const sizes = [
  '45,5',
  'S',
  'XXS',
  'XXL',
  'XS',
  '4XL',
  'One Size',
  '0',
  '32',
  '42,5',
  '18',
  'XXS/XS',
  'XXXS',
  'L'
];

As a first step I would create buckets for the corresponding regular expressions and if a match exists I push that value to the bucket, like so:

function exampleSort() {
  const bucket = Array.from(new Array(sizeOrder.length), () => []);

  sizes.forEach(size => {
    const i = sizeOrder.findIndex(order => order.test(size));

    if (i > -1) {
      bucket[i].push(size);
    }
  });
}

After that I'd go through each bucket and sort them accordingly and then join those arrays together to one.

But I have two questions:

What about the special case of XXS/XS? How would I sort that bucket so that XXS/XS would be between XXS and XS?

This seems to be an imperative and naive implementation. Is there any other way to do this more efficiently?

This is my expected output:

const sorted = [
  'One Size',
  'XXXS',
  'XXS',
  'XXS/XS',
  'XS',
  'S',
  'L',
  'XXL',
  '4XL',
  '0',
  '18',
  '32',
  '42,5',
  '45,5'
];

The question seems a bit unclear. Sorting usually involves comparing two items at a time. If we can compare two items reliably, then it would seem to be just a matter of choosing a sorting algorithm. Is the issue here how to reliably compare two items, or which sorting algorithm would be best (given that we can already reliably compare two items)? — גלעד ברקן
– גלעד ברקן, Commented Jan 9, 2019 at 13:14

CertainPerformance · Accepted Answer · 2019-01-09 13:27:44Z

5

One option would be to iterate through the strings, pushing to a Map of arrays indexed by the matching regular expression. Then, sort each array, and flatten to get the result.

Note the addition of ^ and $ anchors to ensure that only full matches fulfill a .test.

const sizeOrder = [
  /^One Size$/,
  /^[X/S]+S$/i,
  /^S$/i,
  /^M$/i,
  /^L$/i,
  /^[X]+L$/i,
  /^[4-9]XL$/i,
  /^[0-9,]+$/,
];
const patternMap = new Map(sizeOrder.map(pattern => [pattern, []]));
const sizes = [
  '45,5',
  'S',
  'XXS',
  'XXL',
  'XS',
  '4XL',
  'One Size',
  '0',
  '32',
  '42,5',
  '18',
  'XXS/XS',
  'XXXS',
  'L'
];
sizes.forEach((str) => {
  const matchingPattern = sizeOrder.find(pattern => pattern.test(str));
  patternMap.get(matchingPattern).push(str);
});
const valuesArr = [...patternMap.values()];
valuesArr.forEach(arr => arr.sort((a, b) => b.localeCompare(a)));
// sort the last one from /^[0-9,]+$/ differently:
valuesArr[valuesArr.length - 1].sort();
console.log(valuesArr.flat());

Or, using an array of patterns and an optional associated sorting function, you could do something like:

const sizeOrder = [
  { pattern: /^One Size$/ },
  { pattern: /^[X/S]+S$/i, }, // insert your custom sort logic for XXS/XS here
  { pattern: /^S$/i },
  { pattern: /^M$/i },
  { pattern: /^L$/i },
  { pattern: /^[X]+L$/i },
  { pattern: /^[4-9]XL$/i },
  { pattern: /^[0-9,]+$/, sort: arr => arr.sort() }
];
const patternMap = new Map(sizeOrder.map(({ pattern }) => [pattern, []]));
const sizes = [
  '45,5',
  'S',
  'XXS',
  'XXL',
  'XS',
  '4XL',
  'One Size',
  '0',
  '32',
  '42,5',
  '18',
  'XXS/XS',
  'XXXS',
  'L'
];
sizes.forEach((str) => {
  const { pattern } = sizeOrder.find(({ pattern }) => pattern.test(str));
  patternMap.get(pattern).push(str);
});
const valuesArr = [...patternMap.values()];
valuesArr.forEach((arr, i) => {
  const sort = sizeOrder[i].sort;
  if (sort) {
    sort(arr);
  } else {
    arr.sort((a, b) => b.localeCompare(a));
  }
});
console.log(valuesArr.flat());

edited Jan 9, 2019 at 13:27

answered Jan 9, 2019 at 12:53

CertainPerformance

373k55 gold badges354 silver badges359 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Johannes Klauß Over a year ago

This works excellent, but the XXS/XS value gets sorted before XXS and XS, but it should be inbetween.

CertainPerformance Over a year ago

Your different regexes look to have different sorting rules for the arrays of strings they match. Maybe use an array of objects instead of an array of patterns, and have the objects contain an optional sorting function? I'm not sure what sort of sorting logic you want for them all

Johannes Klauß Over a year ago

I think that this is the main problem I am after. Is it possible to somehow generically get XXS/XS sorted inbetween XXS and XS without defining a super special rule.

CertainPerformance Over a year ago

Not really, not without knowing some logic behind why it's sorted like that instead of as what the plain localeCompare would result in

CertainPerformance Over a year ago

I could make up some very strange looking logic to produce the result you're looking for, but it would make much more sense if there was a general rule to why it's sorted the way it is - once you figure out what it is, just put it as a sort property of the /^[X/S]+S$/i pattern

Nina Scholz · Accepted Answer · 2019-01-09 14:33:47Z

You could use a staged approach by checking

if the string conteins a slash, then split this string and take the average value for it,
if some other patterns are in the string, then return a value, reflecting the order or together with an offset a value for 'S', 'M' 'L',
if the string contains some leading 'X' or a digit followed by 'S' or 'L', then get the number or the count of starting 'X' and use a factor for moving the value to the right direction.

const
    getOrder = s => {
        var standard = { s: -0.5, m: 0, l: 0.5 },
            x = 0;
        if (s.includes('/')) return s.split('/').map(getOrder).reduce((a, b) => a + b) / 2;
        if (/^One Size$/.test(s)) return 1;
        if (/^[lms]$/i.test(s)) return standard[s.toLowerCase()] + 2;
        if (/x+[sl]$/i.test(s)) {
            if (/^\dx/i.test(s)) {
                x = s[0];
            } else {
                while (s[x].toLowerCase() === 'x') x++;
            }
            return standard[s.slice(-1).toLowerCase()] * (1 + 0.01 * x) + 2;
        }
        if (/^[0-9,]+$/.test(s)) return 3;
        return 0;
    },
    sizes = ['45,5', 'S', 'XXS', 'XXL', 'XS', '4XL', 'One Size', '0', '32', '42,5', '18', 'XXS/XS', 'XXXS', 'L', 'M'];

sizes.sort((a, b) => getOrder(a) - getOrder(b) || a.replace(',', '.') - b.replace(',', '.'));

console.log(sizes);

.as-console-wrapper { max-height: 100% !important; top: 0; }

Collectives™ on Stack Overflow

JavaScript: Algorithm for sorting based on an predefined order of Regexes

2 Answers 2

5 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

5 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related