정렬 알고리즘은 단순히 줄 세우기가 아니다
크리스는 쇼핑몰 프로젝트에서 "가격 낮은 순", "최신순" 필터 기능을 구현하고 있다.
자바스크립트에는 천하무적 .sort() 메서드가 있다. 크리스는 고민 없이 코드를 작성했다.
const products = [
{ name: "키보드", price: 30000 },
{ name: "마우스", price: 15000 },
{ name: "모니터", price: 200000 }
];
// 가격 오름차순 정렬
products.sort((a, b) => a.price - b.price);기능은 완벽하게 동작한다. 하지만 문득 궁금해졌다.
"면접에서는 왜 퀵 정렬이니 병합 정렬이니 하는 걸 물어볼까? 실무에선 그냥 sort() 한 방이면 끝나는데?"
"그리고 상품이 100만 개가 되어도 이 코드가 빠를까?"
우리가 정렬 알고리즘을 배워야 하는 이유는 단순히 숫자를 나열하기 위해서가 아니다. 정렬은 모든 효율적인 알고리즘의 시작점이기 때문이다.
1. 정렬은 검색의 전제 조건이다
우리가 도서관에 갔다고 상상해 보자. 책들이 아무 순서 없이 바닥에 널브러져 있다면, 원하는 책을 찾기 위해 처음부터 끝까지 하나씩 확인(O(N))해야 한다. 책이 10만 권이라면 며칠이 걸릴 것이다.
하지만 책들이 '장르별 -> 가나다순'으로 정렬되어 있다면?
우리는 중간쯤을 펴보고, "어? 'ㅎ'이네? 그럼 더 앞쪽이겠구나"라며 탐색 범위를 절반씩 줄여나갈 수 있다. 이것이 바로 이진 탐색(Binary Search)이며, 시간 복잡도는 O(log N)으로 획기적으로 줄어든다.
즉, 데이터를 정렬해두는 비용을 투자하면, 이후의 검색 비용을 평생 아낄 수 있다. 정렬은 데이터를 효율적으로 다루기 위한 '인프라 구축' 단계다.
2. 정렬의 보이지 않는 특성: 안정성 (Stability)
정렬 알고리즘을 선택할 때 꼭 고려해야 하는 중요한 개념이 있다. 바로 안정성(Stable vs Unstable)이다.
안정 정렬이란, "중복된 키값의 순서가 정렬 후에도 유지되는가?"를 의미한다.
상황: 크리스가 상품 목록을 "이름순"으로 먼저 정렬했다. 그 상태에서 다시 "가격순"으로 정렬했다.
UI 관점에서 이는 매우 중요하다. 엑셀에서 필터를 여러 번 걸 때 순서가 유지되는 것이 바로 이 '안정 정렬' 덕분이다. (참고로 자바스크립트의 sort()는 ES2019부터 안정 정렬을 보장한다.)
3. 왜 이렇게 종류가 많을까?
버블, 선택, 삽입, 퀵, 병합, 힙... 이름도 다양하다. 왜 완벽한 하나를 쓰지 않고 이렇게 많은 알고리즘이 존재할까?
브라우저마다 Array.prototype.sort의 내부 구현이 다른 이유도 이 때문이다. (과거 크롬 V8은 퀵 정렬을 썼지만, 지금은 안정성을 위해 병합 정렬과 삽입 정렬을 섞은 TimSort를 사용한다.)
4. 우리가 배울 여정
이제부터 우리는 알고리즘의 진화 과정을 따라가 볼 것이다.
핵심 정리
자, 이제 첫 번째 타자는 가장 유명하고 가장 쉬운 녀석이다.
거품이 보글보글 올라오는 것처럼 데이터를 정렬한다고 해서 이름 붙여진 버블 정렬(Bubble Sort). 비효율의 대명사지만, 정렬의 기본 원리를 이해하는 데는 최고다.