JavaScript での安定した並べ替え

目的: 一貫性と安定性を維持しながら、キーに基づいてオブジェクトの配列を効率的に並べ替えます。

アルゴリズムの推奨事項: 多くの並べ替えアルゴリズムが存在しますが、特定の安定性が必要な場合は、QuickSort や MergeSort などの非安定な並べ替えアルゴリズムの修正バージョンを実装することを検討してください。

安定した並べ替え手法:

安定性を確保するために、並べ替え比較関数に追加の基準を追加します。具体的には、2 つの等しい要素を比較する場合、入力配列内の元の位置をタイブレーカーとして使用します。これにより、同じキーを持つ要素の順序が維持されます。

JavaScript 実装:

const stableSort = (arr, key, order) => {
  // Get initial positions of elements
  const positions = arr.map((el, i) => i);

  // Sort using modified comparison function
  arr.sort((a, b) => {
    const keyA = a[key];
    const keyB = b[key];

    if (keyA === keyB) {
      // Fall back to position for stability
      return positions[a] - positions[b];
    }

    return order === "asc" ? keyA - keyB : keyB - keyA;
  });

  return arr;
};

使用例:

const arr = [
  { id: 1, value: 4 },
  { id: 2, value: 2 },
  { id: 3, value: 4 },
  { id: 4, value: 3 },
];

const sortedArr = stableSort(arr, "value", "asc");

// Output:
// [
//   { id: 2, value: 2 },
//   { id: 1, value: 4 },
//   { id: 3, value: 4 },
//   { id: 4, value: 3 },
// ]

この手法を使用すると、安定していない並べ替えアルゴリズムでも安定した並べ替えを行うことができるため、約 200 ～ 300 個のオブジェクトのシナリオに適しています。