JavaScript の安定した並べ替えアルゴリズム

データを並べ替えるとき、等しい要素の元の順序を維持することは、安定した並べ替えアルゴリズムにとって重要です。このコンテキストでは、要素の順序の一貫性を維持しながら、特定のキーを持つオブジェクトの配列を特定の順序でソートすることを目的としています。

安定したソート手法

興味深いことに、非安定ソート機能を使用すると、安定したソートを実現できます。並べ替え前に各要素の初期位置を取得することで、位置を 2 番目の基準として使用して並べ替え比較の関係を解消できます。

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

使用例

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

この手法により安定したソートが可能になりますJavaScript では、等しい値を持つ要素の元の順序が維持されます。