Stabile Sortieralgorithmen in JavaScript

Beim Sortieren von Daten ist die Beibehaltung der ursprünglichen Reihenfolge gleicher Elemente für stabile Sortieralgorithmen von entscheidender Bedeutung. In diesem Zusammenhang zielen wir darauf ab, ein Array von Objekten mit einem bestimmten Schlüssel in einer bestimmten Reihenfolge zu sortieren und dabei die Konsistenz der Elementreihenfolge beizubehalten.

Stabile Sortiertechnik

Interessanterweise sogar Instabile Sortierfunktionen können eine stabile Sortierung erreichen. Indem wir die Anfangsposition jedes Elements vor dem Sortieren erfassen, können wir Unentschieden im Sortiervergleich auflösen, indem wir die Position als sekundäres Kriterium verwenden.

Implementierung in 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);
};

Beispielverwendung

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 }]

Diese Technik ermöglicht eine stabile Sortierung in JavaScript unter Beibehaltung der ursprünglichen Reihenfolge von Elementen mit gleichen Werten.