데이터를 다루는 개발자에게 '정렬(Sorting)'은 숨 쉬는 것과 같습니다. 쇼핑몰에서 '낮은 가격순'을 누르거나, 엑셀에서 '가나다순' 정렬을 하는 등 우리는 항상 정렬된 데이터를 소비합니다. 하지만 컴퓨터 내부에서는 이 정렬을 수행하기 위해 수많은 교환과 비교 작업이 일어납니다. 오늘은 정렬 알고리즘의 조상님이자, 알고리즘적 사고의 기초가 되는 두 가지 방법, 버블 정렬(Bubble Sort)과 선택 정렬(Selection Sort)에 대해 알아보겠습니다. 비록 실무에서 대량의 데이터를 처리할 때 쓰기에는 느리지만(O(n^2)), 이들이 어떻게 동작하는지 이해하는 것은 효율적인 코드를 짜기 위한 첫걸음입니다.
1. 정렬(Sorting)이란 무엇인가?
정렬은 무작위로 섞여 있는 데이터를 특정 기준(오름차순 또는 내림차순)에 맞춰 순서대로 나열하는 작업입니다. 정렬이 되어 있지 않다면 이진 탐색(Binary Search) 같은 고속 검색 알고리즘을 사용할 수 없기 때문에, 정렬은 데이터 검색의 전처리 과정으로서 매우 중요합니다.
2. 버블 정렬 (Bubble Sort): 거품처럼 올라온다
버블 정렬은 인접한 두 데이터를 비교하여, 순서가 잘못되어 있으면 자리를 바꾸는(Swap) 방식을 처음부터 끝까지 반복하는 알고리즘입니다. 이 과정에서 가장 큰 값이 마치 물속의 거품이 수면 위로 올라오듯 맨 뒤로 이동한다고 하여 '버블 정렬'이라는 귀여운 이름이 붙었습니다.
2-1. 동작 원리 (오름차순 기준)
- 배열의 첫 번째 값과 두 번째 값을 비교합니다. 앞의 값이 더 크다면 두 수의 자리를 바꿉니다.
- 두 번째 값과 세 번째 값을 비교합니다. 역시 앞이 더 크다면 바꿉니다.
- 이 과정을 끝까지 반복하면, 제일 큰 값이 맨 오른쪽(마지막) 자리에 확정됩니다.
- 이제 맨 마지막 값은 정렬이 끝났으므로 제외하고, 나머지 데이터들로 1번부터 다시 반복합니다.
2-2. 장단점 분석
- 장점: 구현이 너무나도 단순합니다. 코드가 직관적이라 이해하기 쉽습니다.
- 단점: 매우 느립니다. 데이터가 N개일 때, $N \times N$번의 비교가 필요하므로 시간 복잡도가 O(n^2)입니다. 데이터가 10,000개만 넘어가도 사용하기 힘듭니다. 또한, 불필요한 자리 교환(Swap)이 너무 많이 일어납니다.
3. 선택 정렬 (Selection Sort): 너만 보인단 말이야
선택 정렬은 이름 그대로 "가장 작은 것을 선택해서 앞으로 보낸다"는 직관적인 아이디어로 만들어졌습니다. 버블 정렬이 옆 사람과 계속 자리를 바꾼다면, 선택 정렬은 전체를 훑어보고 딱 한 놈만 골라냅니다.
3-1. 동작 원리 (오름차순 기준)
- 배열 전체를 훑어서 가장 작은 값(최솟값)을 찾습니다.
- 그 최솟값을 배열의 맨 첫 번째 값과 자리를 바꿉니다. (이제 첫 번째 자리는 정렬 완료)
- 첫 번째 값을 제외한 나머지 범위에서 다시 최솟값을 찾습니다.
- 그 값을 두 번째 자리와 바꿉니다. 이 과정을 끝까지 반복합니다.
3-2. 장단점 분석
- 장점: 버블 정렬보다 자리 교환(Swap) 횟수가 훨씬 적습니다. 버블 정렬은 비교할 때마다 바꾸지만, 선택 정렬은 한 번의 회전(Pass) 당 딱 한 번만 바꿉니다. 따라서 데이터 교환 비용이 비싼 시스템에서는 버블 정렬보다 유리합니다.
- 단점: 여전히 느립니다. 비교 횟수는 버블 정렬과 마찬가지로 O(n^2)입니다. 데이터가 이미 정렬되어 있더라도 끝까지 최솟값을 찾아야 하므로 효율이 좋지 않습니다.
4. 비교 및 요약
두 알고리즘 모두 성능 면에서는 합격점을 주기 어렵습니다. 현대의 시스템 정렬 함수(`Array.sort()` 등)는 대부분 퀵 정렬이나 병합 정렬을 사용하여 O(n log n)의 속도를 냅니다. 하지만 버블 정렬과 선택 정렬은 알고리즘의 '불변식(Invariant)'과 '루프 구조'를 이해하는 데 있어 최고의 교보재입니다.
1. 버블 정렬은 인접한 두 수를 비교/교환하며 큰 수를 뒤로 보내는 방식입니다. (교환이 많음)
2. 선택 정렬은 전체 중 최솟값을 찾아 앞쪽으로 가져오는 방식입니다. (교환이 적음)
3. 둘 다 시간 복잡도는 O(n^2)로, 학습용으로는 좋으나 실무 대용량 처리에는 적합하지 않습니다.