Algoritmos de clasificación estables en JavaScript

Al ordenar datos, preservar el orden original de elementos iguales es crucial para algoritmos de clasificación estables. En este contexto, nuestro objetivo es ordenar una serie de objetos con una clave específica en un orden determinado manteniendo la coherencia del orden de los elementos.

Técnica de clasificación estable

Curiosamente, incluso las funciones de clasificación no estables pueden lograr una clasificación estable. Al capturar la posición inicial de cada elemento antes de ordenar, podemos romper empates en la comparación de clasificación usando la posición como criterio secundario.

Implementación en 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);
};

Ejemplo 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 una clasificación estable en JavaScript, preservando el orden original de elementos con valores iguales.