JavaScript의 안정적인 정렬

목표: 일관성과 안정성을 유지하면서 키를 기반으로 객체 배열을 효율적으로 정렬합니다.

알고리즘 권장 사항: 많은 정렬 알고리즘이 존재하지만 특정 안정성 요구 사항에 따라 다음을 구현하는 것을 고려하십시오. QuickSort 또는 MergeSort와 같은 비안정 정렬 알고리즘의 수정된 버전입니다.

안정 정렬 기술:

안정성을 보장하려면 정렬 비교 기능에 추가 기준을 추가하세요. . 특히 두 개의 동일한 요소를 비교할 때 입력 배열의 원래 위치를 순위 결정자로 사용합니다. 이는 동일한 키를 가진 요소의 순서를 유지합니다.

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개 개체의 시나리오에 적합합니다.