Algoritmos de classificação estáveis ​​em JavaScript

Ao classificar dados, preservar a ordem original de elementos iguais é crucial para algoritmos de classificação estáveis. Neste contexto, pretendemos classificar uma matriz de objetos com uma chave específica em uma determinada ordem, mantendo a consistência da ordem dos elementos.

Técnica de classificação estável

Curiosamente, mesmo funções de classificação não estáveis ​​podem alcançar uma classificação estável. Ao capturar a posição inicial de cada elemento antes da classificação, podemos desempate na comparação da classificação usando a posição como critério secundário.

Implementação em JavaScript

const sortBy = (arr, key, order) => {
  // Capture element positions
  const positions = arr.map((item, i) => {
    return { item, position: i };
  });

  // Perform sorting
  positions.sort((a, b) => {
    let cmp = a.item[key].localeCompare(b.item[key]);
    if (cmp === 0) {
      // Tiebreaker: sort by position
      cmp = a.position - b.position;
    }
    if (order === "desc") {
      return cmp * -1;
    } else {
      return cmp;
    }
  });

  // Return sorted objects
  return positions.map(position => position.item);
};

Exemplo de uso

const data = [
  { name: "Alice", age: 25 },
  { name: "Bob", age: 30 },
  { name: "Eve", age: 25 },
];

const sortedAscending = sortBy(data, "age", "asc");
console.log(sortedAscending); // [{ name: "Alice", age: 25 }, { name: "Eve", age: 25 }, { name: "Bob", age: 30 }]

const sortedDescending = sortBy(data, "age", "desc");
console.log(sortedDescending); // [{ name: "Bob", age: 30 }, { name: "Eve", age: 25 }, { name: "Alice", age: 25 }]

Esta técnica permite classificação estável em JavaScript, preservando a ordem original dos elementos com valores iguais.