[잡담] Create React App에서 나오는 현대 JS는 이미 Array#sort가 안정정렬임을 보장함

telnet turtle·2022년 12월 27일
0

들어가며

Create React App을 사용하며 프로젝트를 생성하며 나오는 프롬프트에서 다음과 같은 메시지를 읽었다.

warning react-scripts > css-minimizer-webpack-plugin > cssnano > cssnano-preset-default > postcss-svgo > svgo > stable@0.1.8: Modern JS already guarantees Array#sort() is a stable sort, so this library is deprecated. See the compatibility table on MDN: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/sort#browser_compatibility

내가 생각하고 있던 것

처음에는, JS Array#sort가 안정정렬이라고 알고 있었다. 다음엔 안정정렬임을 보장하지 않는다고 MDN에서 읽었었다. 이제와서는 또 안정정렬이라네? 이게 어떻게 된 것일까?

확인하기

한국어 MDN의 Array.prototype.sort()를 보면,

sort() 메서드는 배열의 요소를 적절한 위치에 정렬한 후 그 배열을 반환합니다. 정렬은 stable sort
가 아닐 수 있습니다. 기본 정렬 순서는 문자열의 유니코드 코드 포인트를 따릅니다.

내가 안정정렬이 아니라고 알게 된 원인이다.

영문 MDN의 동문서를 보면,

  • Stable: The comparator returns the same result with the same pair of input.

안정정렬(stable sort)이 맞잖아?

Sort stability

Since version 10 (or ECMAScript 2019), the specification dictates that Array.prototype.sort is stable.

안정정렬이란 무엇인가?

위에서 언급한 영문 MDN의 Sort stability 부분을 보면,

예를 들어 이와같은 4명의 학생이 있다고 가정하자. 14세 김철수, 15세 배철수, 15세 신철수, 13세 이철수.

이 학생 목록을 나이순으로 안정정렬하면,

13세 이철수, 14세 김철수, 15세 배철수, 15세 신철수

가 된다. 이 때, 원래 순서인 배철수, 신철수가 정렬 후에도 똑같은 순서로 남아있는 것이 안정정렬이다. 안정정렬 알고리즘은 이 순서가 보존되는것을 보장한다.

마저읽기

ECMAScript 2019 이전엔 안정정렬임이 보장되지 않았다고 한다. 그 말은, 정렬 후에 15세 신철수, 15세 배철수가 될 수 있다는 의미이다.

마무리

About the stability of the algorithm used by V8 engine 문서에 따르면, 요약하자면 V8의 Array#sort 구현이 퀵정렬에서 삽입정렬로 바뀌며 안정성을 획득할 수 있었다고 한다. 그리고 상세 알고리즘과 어려움, Torque와 임시배열에 대해서도 설명한다. Happy sorting, and thank you for reading and have a nice day!

profile
프론트엔드 엔지니어

0개의 댓글