JavaScript 안정 정렬

Stable sort란?

정렬 기준에 차이가 없다면 원래 입력에서 주어진 순서를 유지하는 정렬을 말합니다. 만약 두 항목이 같은 값을 가지면 그들의 순서가 정렬된 리스트에 유지됩니다. (values that have the same key keep their original order)

Stable sorting algorithms maintain the relative order of records with equal keys. [...] Whenever there are two records (let's say R and S) with the same key, and R appears before S in the original list, then R will always appear before S in the sorted list. [Sorting Algorithm - Wikipedia]

Stable Srot 알고리즘

• 병합 정렬(merge sort)
• 버블 정렬(bubble sort)
• 삽입 정렬(insertion sort)

Javascript의 Array.Sort()

Array.sort()는 stable sort가 아닐 수도 있습니다. 브라우저마다 사용하는 정렬 알고리즘이 다르기 때문입니다. 특히 V8엔진은 배열 length가 10 이하면 insertion sort를, 초과면 quick sort를 사용하므로 긴 배열에 대해서는 stable sort가 아닙니다. V8엔진의 경우 버전 7.0이후로는 항상 stable sort를 제공한다고 합니다!

 

정렬을 항상 stable 하게 만들기 위해 DSU 패턴을 사용할 수 있습니다. 정렬 수행 전 각 엘리먼트에 인덱스 값을 부여해 줍니다. 만약 key값이 같으면 인덱스 값을 비교합니다.

const list = Array.from({ length: 30 }, (val, idx) => ({
  key: Math.floor(Math.random() * (10 - 1)) + 1,
  orgnIdx: idx
}));

list.forEach((elem, idx) => {
    elem.position = idx;
});

const compare = (a, b) => {
  if (a.key === b.key) return a.position - b.position;
  if (a.key < b.key) return -1;
  return 1;
};

list.sort(compare);

 

코드 샘플 링크

참조

• 카카오신입 공채 3차 코딩 테스트 문제 해설 3번 문항
• 자바스크립트 크롬의 불안정한 배열 정렬 문제 - Javascript chrome-v8 Unstable sorting problem
• Vjeux, Javascript – Sorting Table