[JavaScript] 안정 정렬 vs 불안정 정렬: JavaScript `sort()` 메서드의 숨겨진 진실

안정 정렬 vs 불안정 정렬: JavaScript sort() 메서드의 숨겨진 진실

JavaScript에서 배열을 정렬할 때 흔히 사용하는 sort() 메서드, 과연 완벽할까? 오늘은 sort() 메서드의 숨겨진 진실, 바로 안정 정렬과 불안정 정렬에 대해 알아보겠다.

안정 정렬(Stable Sort)이란?

안정 정렬은 정렬 후에도 동일한 값을 가진 요소들의 원래 순서가 그대로 유지되는 정렬 알고리즘이다. 마치 질서정연한 줄 세우기처럼, 키가 같은 사람들은 원래 서 있던 순서대로 줄을 서는 것이다.

불안정 정렬(Unstable Sort)이란?

반면 불안정 정렬은 동일한 값을 가진 요소들의 원래 순서가 바뀔 수 있는 정렬 알고리즘이다. 키가 같은 사람들의 순서가 뒤죽박죽 섞일 수도 있다는 뜻이다.

JavaScript sort() 메서드는 과연 안정적일까?

ECMAScript 표준에서는 sort() 메서드의 안정성에 대해 명확하게 규정하고 있지 않는다. 따라서 JavaScript 엔진(Chrome V8, Firefox SpiderMonkey 등)에 따라 안정 정렬로 구현될 수도, 불안정 정렬로 구현될 수도 있다.

간단한 예제로 확인해볼까요?

const products = [
  { name: "Product A", price: 20 },
  { name: "Product B", price: 10 },
  { name: "Product C", price: 20 },
  { name: "Product D", price: 10 },
];

products.sort((a, b) => a.price - b.price);

console.log(products);

위 코드의 실행 결과는 JavaScript 엔진에 따라 다를 수 있다.

• 안정 정렬 엔진: Product B와 Product D의 순서, Product A와 Product C의 순서가 원래대로 유지된다.

  [
    { name: "Product B", price: 10 },
    { name: "Product D", price: 10 },
    { name: "Product A", price: 20 },
    { name: "Product C", price: 20 }
  ]

• 불안정 정렬 엔진: 동일한 가격을 가진 제품들의 순서가 뒤바뀔 수 있다.

  [
    { name: "Product D", price: 10 },
    { name: "Product B", price: 10 },
    { name: "Product C", price: 20 },
    { name: "Product A", price: 20 }
  ]

안정 정렬을 "확실하게" 보장받고 싶다면?

만약 안정 정렬이 "반드시" 필요한 상황이라면, 다음과 같이 인덱스를 활용하여 정렬 순서를 명확하게 지정할 수 있다.

const productsWithIndex = products.map((product, index) => ({
  ...product,
  index,
}));

productsWithIndex.sort((a, b) => {
  if (a.price !== b.price) {
    return a.price - b.price;
  }
  return a.index - b.index; // 가격이 같으면 인덱스 순으로 정렬
});

console.log(productsWithIndex);

이제 어떤 JavaScript 엔진을 사용하더라도 Product B가 Product D보다, Product A가 Product C보다 먼저 나타나는 것을 보장할 수 있다.

결론

JavaScript sort() 메서드를 사용할 때는 안정 정렬 여부가 엔진에 따라 다를 수 있다는 점을 기억해야 한다. 안정 정렬이 꼭 필요한 경우에는 인덱스를 활용하는 방법을 고려하여 의도한 대로 동작하는 코드를 작성하자!