개발자가 다루는 데이터의 90% 이상은 정렬(Sorting)이 필요합니다. 쇼핑몰의 '낮은 가격순', 게시판의 '최신순', 엑셀의 '가나다순' 등 정렬은 우리 생활 깊숙이 들어와 있습니다. 수많은 정렬 알고리즘이 존재하지만, 그중에서도 가장 기본이 되며 알고리즘적 사고의 기초를 다져주는 두 가지 방법이 있습니다. 바로 버블 정렬(Bubble Sort)과 선택 정렬(Selection Sort)입니다. 비록 $O(N^2)$이라는 느린 속도 때문에 실무에서 대량의 데이터를 처리할 때는 잘 쓰이지 않지만, 이들이 데이터를 비교하고 교환하는 원리를 이해하는 것은 더 복잡한 알고리즘을 배우기 위한 필수 코스입니다.
1. 버블 정렬(Bubble Sort): 인접한 놈과 싸운다
버블 정렬은 이름처럼 데이터가 물방울(Bubble)이 수면 위로 떠 오르듯 정렬되는 모습을 보입니다. 핵심 원리는 "바로 옆에 있는 놈이랑만 비교해서 자리를 바꾼다"입니다.
1-1. 동작 과정 (오름차순 예시)
숫자 `[5, 3, 8, 1]`을 정렬해 봅시다. 1. 첫 번째 `5`와 두 번째 `3`을 비교합니다. `5`가 더 크네요? 자리를 바꿉니다(Swap). -> `[3, 5, 8, 1]` 2. 두 번째 `5`와 세 번째 `8`을 비교합니다. `5`가 더 작으니 그대로 둡니다. 3. 세 번째 `8`과 네 번째 `1`을 비교합니다. `8`이 더 크니 자리를 바꿉니다. -> `[3, 5, 1, 8]` 4. 1회전이 끝났습니다. 가장 큰 `8`이 맨 뒤로 이동했습니다. 5. 이제 맨 뒤의 `8`은 확정되었으니, 나머지 `[3, 5, 1]`을 가지고 처음부터 다시 반복합니다.
1-2. 장점과 단점
- 장점: 구현이 너무나도 쉽습니다. 코드가 직관적이라 초보자가 이해하기 가장 좋습니다.
- 단점: 매우 느립니다. 최악의 경우 $N \times N$번 비교해야 하므로 시간 복잡도가 $O(N^2)$입니다. 또한, 자리를 바꾸는 연산(Swap)이 너무 빈번하게 일어나서 실제 성능도 좋지 않습니다.
2. 선택 정렬(Selection Sort): 한 놈만 팬다
버블 정렬이 옆 사람과 계속 투닥거린다면, 선택 정렬은 전체를 훑어보고 "가장 작은 놈 하나만 골라내서" 앞으로 보내는 방식입니다.
2-1. 동작 과정 (오름차순 예시)
똑같이 `[5, 3, 8, 1]`을 정렬해 봅시다. 1. 전체 배열을 쭉 훑어서 최솟값을 찾습니다. `1`이네요. 2. 이 `1`을 맨 앞에 있는 `5`와 자리를 바꿉니다. -> `[1, 3, 8, 5]` 3. 이제 첫 번째 `1`은 정렬이 끝났습니다. 4. 두 번째 칸부터 끝까지 중에서 다시 최솟값을 찾습니다. `3`이네요. 자기 자리니 그대로 둡니다. 5. 세 번째 칸부터 끝까지 중에서 최솟값을 찾습니다. `5`네요. `8`과 바꿉니다. -> `[1, 3, 5, 8]`
2-2. 장점과 단점
- 장점: 버블 정렬보다 교환(Swap) 횟수가 훨씬 적습니다. 버블 정렬은 비교할 때마다 바꾸지만, 선택 정렬은 한 번 스캔할 때 딱 한 번만 바꿉니다. 따라서 쓰기(Write) 작업이 비싼 메모리 환경에서는 선택 정렬이 유리할 수 있습니다.
- 단점: 여전히 느립니다. 비교 횟수는 버블 정렬과 마찬가지로 $O(N^2)$입니다. 데이터가 이미 정렬되어 있더라도 끝까지 최솟값을 찾아야 하므로 효율이 좋지 않습니다.
3. 둘의 결정적 차이 요약
두 알고리즘 모두 성능 면에서는 낙제점이지만, 동작 방식의 차이를 아는 것이 중요합니다.
| 구분 | 버블 정렬 (Bubble Sort) | 선택 정렬 (Selection Sort) |
|---|---|---|
| 핵심 로직 | 인접한 두 수를 계속 비교/교환 | 최솟값을 찾아 해당 위치로 이동 |
| 교환 횟수 | 매우 많음 (Worst) | 적음 (회전당 1회) |
| 시간 복잡도 | $O(N^2)$ | $O(N^2)$ |
1. 버블 정렬은 인접한 데이터를 교환하며 큰 값을 뒤로 보내는, 구현이 가장 쉬운 알고리즘입니다.
2. 선택 정렬은 최솟값을 선택해 앞으로 보내는 방식으로, 버블 정렬보다 교환 횟수가 적습니다.
3. 둘 다 $O(N^2)$의 시간 복잡도를 가지므로 데이터가 많을 때는 퀵 정렬 등을 써야 합니다.