JavaScript의 안정적인 정렬 알고리즘

데이터를 정렬할 때 안정적인 정렬 알고리즘을 위해서는 동일한 요소의 원래 순서를 유지하는 것이 중요합니다. 이러한 맥락에서 우리는 요소 순서 일관성을 유지하면서 특정 키를 사용하여 객체 배열을 지정된 순서로 정렬하는 것을 목표로 합니다.

안정적인 정렬 기술

흥미롭게도 불안정한 정렬 기능을 사용하면 안정적인 정렬이 가능합니다. 정렬하기 전에 각 요소의 초기 위치를 캡처함으로써 위치를 보조 기준으로 사용하여 정렬 비교에서 관계를 끊을 수 있습니다.

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에서는 동일한 값을 가진 요소의 원래 순서를 유지합니다.