sort함수의 비밀과 주의점
크리스는 이제 정렬 알고리즘 전문가가 되었다.
버블, 선택, 삽입, 퀵, 합병, 힙, 기수 정렬까지 섭렵했다.
"좋아, 이제 실무에 적용해 볼까?"
크리스는 숫자 배열을 정렬하는 코드를 짰다.
const numbers = [2, 1, 10, 3, 5];
numbers.sort();
console.log(numbers);
// 기대한 결과: [1, 2, 3, 5, 10]
// 실제 결과: [1, 10, 2, 3, 5] <-- ?!?!?!"아니, 10이 왜 2보다 앞에 있어? 자바스크립트는 수학도 못해?"
크리스는 당황했다. 퀵 정렬을 구현할 줄 알면 뭐하나, 정작 매일 쓰는 sort()가 왜 이렇게 동작하는지 모르는데.
2장의 마지막 시간은 우리가 숨 쉬듯 사용하는 Array.prototype.sort()의 치명적인 함정과, 브라우저가 숨기고 있는 내부 알고리즘의 정체에 대해 알아본다.
1. 함정: 왜 숫자를 문자로 생각할까?
자바스크립트의 sort()는 인자(Comparator)를 넘기지 않으면, 기본적으로 모든 데이터를 문자열(String)로 변환한 뒤 유니코드 순서대로 정렬한다.
이것이 10이 2보다 먼저 오는 이유다. 사전에서 "Apple"이 "Banana"보다 먼저 나오듯이, 문자열 "10"은 "1"로 시작하기 때문에 "2"보다 앞자리에 위치한다.
해결책: 비교 함수(Comparator) 제공하기
숫자를 크기대로 정렬하려면 반드시 비교 함수를 넣어줘야 한다.
// 오름차순
numbers.sort((a, b) => a - b);
// 내림차순
numbers.sort((a, b) => b - a);2. 비밀: 브라우저는 어떤 정렬 알고리즘을 쓸까?
우리가 sort()를 호출할 때, 브라우저 내부(엔진)에서는 무슨 일이 벌어질까?
퀵 정렬? 합병 정렬?
과거에는 브라우저마다 제각각이었다. 크롬(V8)은 퀵 정렬을 썼고, 파이어폭스는 합병 정렬을 썼다. 그래서 크롬에서는 '불안정 정렬'이고 파이어폭스에서는 '안정 정렬'인 혼란한 시절이 있었다.
하지만 ECMAScript 2019(ES10)부터 "반드시 안정 정렬(Stable Sort)이어야 한다"는 스펙이 추가되었다.
이에 맞춰 현재 대부분의 모던 브라우저(V8 엔진 포함)는 TimSort라는 알고리즘을 사용한다.
TimSort: 혼종의 미학
TimSort는 파이썬(Python)의 핵심 개발자 Tim Peters가 2002년에 만든 알고리즘이다.
이 녀석은 우리가 배웠던 삽입 정렬(Insertion Sort)과 합병 정렬(Merge Sort)을 아주 영리하게 섞어놨다.
즉, sort()는 마법이 아니라 우리가 배운 알고리즘들의 장점만 합친 하이브리드(Hybrid)다.
3. 리액트 개발자의 주의점: 불변성(Immutability)
sort()에는 또 하나의 함정이 있다. 바로 원본 배열을 변형(Mutate)한다는 것이다.
const original = [3, 1, 2];
const sorted = original.sort();
console.log(original); // [1, 2, 3] <-- 원본이 바뀌어버렸다!
console.log(sorted); // [1, 2, 3]
console.log(original === sorted); // true (같은 참조)리액트(React)에서 state를 이런 식으로 정렬하면 큰일 난다. 리액트는 객체의 참조값이 바뀌어야 리렌더링을 하는데, 원본을 직접 수정하면 변경 사항을 감지하지 못하거나 예기치 않은 버그가 생긴다.
해결책 1: 복사 후 정렬 (Old School)
// 전개 연산자로 복사본을 만들고 정렬한다.
const sorted = [...original].sort((a, b) => a - b);해결책 2: toSorted() (New Standard, ES2023)
2023년에 드디어 원본을 건드리지 않고 새로운 정렬된 배열을 반환하는 메서드가 추가되었다.
const sorted = original.toSorted((a, b) => a - b);
console.log(original); // [3, 1, 2] (유지됨)
console.log(sorted); // [1, 2, 3] (새 배열)리액트 개발자라면 sort 대신 toSorted를 쓰는 습관을 들이자.
4. 2장을 마치며: 정렬, 그 너머로
지금까지 우리는 8가지 정렬 알고리즘과 자바스크립트 내부 구현까지 샅샅이 파헤쳤다.
이제 데이터를 순서대로 나열하는 법을 완벽하게 익혔다.
데이터가 정렬되었다면 무엇을 할 수 있을까? 바로 "원하는 데이터를 빛의 속도로 찾아내는 것"이다.
도서관에 책이 정렬되어 있다면 사서는 1초 만에 책을 찾을 수 있다.
이제 검색(Search)의 세계로 떠날 차례다. 업다운 게임의 필승법부터, 네비게이션이 길을 찾는 원리까지.