서론: 100만 개의 데이터를 정리하라
NASA 위성이 하루에 보내오는 사진은 수만 장입니다. 날짜별로, 혹은 중요도 별로 빠르게 정리(Sorting)하지 않으면 분석 자체가 불가능합니다.
사람이 카드를 정리하듯 하나씩 비교하면 며칠이 걸립니다. 하지만 컴퓨터 과학에는 '퀵 정렬(Quick Sort)'이라는 마법 같은 알고리즘이 있습니다. 이름 그대로 엄청나게 빠릅니다. 오늘 24편에서는 이 알고리즘이 어떻게 작동하는지 '피벗(Pivot)'의 개념으로 알아봅니다.
본론 1: 기준점(Pivot)을 정하고 쪼개라
퀵 정렬의 핵심은 '분할 정복(Divide and Conquer)'입니다.
- 운동장에 100명의 학생이 무작위로 서 있습니다.
- 선생님이 임의로 한 명(기준, Pivot)을 지목합니다. "철수보다 키 작은 사람은 왼쪽, 큰 사람은 오른쪽으로 가!"
- 순식간에 철수를 기준으로 두 그룹으로 나뉩니다.
- 이제 왼쪽 그룹, 오른쪽 그룹에서 또다시 기준을 뽑아 반복합니다.
본론 2: 왜 빠른가? (O(n log n))
지난 16편에서 배운 Big-O를 기억하시나요? 엉성한 정렬(버블 정렬)은 O(n²)이지만, 퀵 정렬은 평균적으로 O(n log n)의 속도를 냅니다.
데이터가 100만 개일 때, 버블 정렬이 1조 번 계산해야 한다면, 퀵 정렬은 약 2,000만 번만 계산하면 됩니다. 알고리즘 하나 바꿨을 뿐인데 속도가 5만 배 빨라지는 것입니다. 이것이 소프트웨어 공학의 위력입니다.
결론: 정리된 데이터가 힘이다
데이터가 정렬되어 있다는 것은, 언제든 원하는 정보를 즉시 찾을 수 있다는 뜻입니다(이진 탐색 가능). 효율적인 시스템을 만들고 싶다면, 데이터를 어떻게 저장하고 정렬할지 고민하십시오. 그 답은 이미 50년 전에 천재들이 만들어 둔 알고리즘 속에 있습니다.