내일배움캠프 42일차 - 자료구조 & 알고리즘 7주차 : 정렬 알고리즘
느린 정렬들 - O(n^2)
버블 정렬 - "옆 사람과 비교"
인접한 두 원소를 비교해서, 순서가 잘못되었으면 교환한다.한 바퀴 돌면 가장 큰 값이 맨 뒤로 떠오른다.
※ 거품이 수면 위로 떠오르듯, 큰 값이 뒤로 밀려나서 버블정렬이다.
예시)
53814 → 35814 → 35814 → 35184 →35148 →
35148 → 35148 → 31548 → 31458 →
31458 → 13458 → 13458 →
13458 → 13458
: 사이클 마다 n → n-1 → n-2 → ... → 총 n(n-1)/2번 비교
→ O(n^2)
선택정렬 - "가장 작은 걸 찾아서 앞에"
전체에서 가장 작은 값을 찾아 첫 번째 위치에 놓고,
나머지는 가장 작은 값을 찾아 두 번째 위치에 놓는 것을 반복.
※ 사람이 눈으로 훑어서 "이게 제일 작네!" 하고 고르는 가장 인간적인 방법이다.
예시)
53814 → 13854 → 13854 →
13854 → 13854 →
13854 → 13458 → 13458 →
13458 → 13458
: 버블교환에 비해 한 사이클 당 교환횟수는 적지만, 값을 전부 비교해서 최솟값을 찾는다.
→ O(n^2)
삽입 정렬 - "카드를 한장씩 끼워넣기"
두 번째 원소부터 시작해서, 이미 정렬된 앞부분에 적절한 위치에 삽입한다.
※ 사람이 카드를 정렬할 대 가장 자연스럽게 하는 방법.
예시)
5 3814 → 35 814 →
35 814 → 358 14 →
358 14 → 1358 4 →
1358 4 → 13458
: 앞 부분은 이미 정렬된 것으로 간주하고 두번째 원소부터 시작, 정렬된 부분의 맨 뒤부터 역순으로 비교해서 적절한 위치에 삽입한다
: 앞 부분의 맨 앞에 삽입되면 모든 원소가 밀림
→ 최악의 경우 O(n^2)
: 단, 이미 한번 정렬된 데이터라면 "끼울 위치 = 제자리" 로 한번만 비교
→ 최선의 경우 O(n)
※ C++ sort() 내부에서도 작은 데이터(~16개)에 활용된다.
세 가지 O(n^2) 정렬 정리
| 정렬 | 전략 | 비교 횟수 | 교환 횟수 | 최선의 경우 |
| 버블 | 인접 비교 | O(n^2) | O(n^2) | O(n^2) |
| 선택 | 최솟값 찾기 | O(n^2) | O(n) | O(n^2) |
| 삽입 | 끼워 넣기 | O(n^2) | O(n^2) | O(n) |
삽입 정렬은 "거의 정렬된 데이터에 강하다" ← 중요
: 이 특성은 C++ sort() 내부에서도 활용된다.
빠른 정렬 - 쪼개서 정렬하기
:
병합 정렬 - 반으로 나누기
1) 각 그룹을 더이상 나눌 수 없을 때 까지 계속 쪼갠다.
53814726 → 5381 4726 → 53 81 47 26 → 5 3 8 1 4 7 2 6
: 원소 1개짜리는 그 자체로 정렬 완료 (base case)
2) 이제 위로 올라가며 정렬된 상태로 합친다.
5 3 8 1 4 7 2 6 → 35 18 47 26 → 1358 2467
: 각 쌍 안에서 작은 값이 왼쪽으로 간다.
3) 정렬된 두 배열을 합칠 때, 양쪽의 가장 앞(가장 작은 값)만 비교한다.
1358( i ) vs 2467( j )
| 단계 | 왼쪽 앞 | 오른쪽 앞 | 선택 | 결과 |
| 1 | 1 | 2 | 왼쪽 (i++) i = 0→1 | [1] |
| 2 | 3 | 2 | 오른쪽 (j++) j = 0→1 | [1, 2] |
| 3 | 3 | 4 | 왼쪽 (i++) i = 1→2 | [1, 2, 3] |
| 4 | 5 | 4 | 오른쪽 (j++) j = 1→2 | [1, 2, 3, 4] |
| 5 | 5 | 6 | 왼쪽 (i++) i = 2→3 | [1, 2, 3, 4, 5] |
| 6 | 8 | 6 | 오른쪽 (j++) j = 2→3 | [1, 2, 3, 4, 5, 6] |
| 7 | 8 | 7 | 오른쪽 (j++) j = 3→(end) | [1, 2, 3, 4, 5, 6, 7] |
| 8 | 8 | - | 왼쪽 (i++) i = 3→(end) | [1, 2, 3, 4, 5, 6, 7, 8] |
※ 이미 정렬되어 있으므로 각 단계는 O(1), 총 n개 → O(n)에 두 배열을 합친다.
4) 모든 단계가 끝나면 정렬 완료.
12345678
: 깊이 log2(8) = 3단계 × 각 단계 O(n)
: 총 비교 수 ≈ 8×3 = 24번 (버블정렬 시 8^2 = 64번)
→ O(n log n)
퀵 정렬 - "기준값으로 나누기"
기준값(pivot)을 정해서, 작은 것/큰 것으로 나누기를 반복한다.
※ C++ sort()는 퀵 정렬을 기반으로 하되, 최악의 경우를 막기 위한 안전장치가 달린 인트로소트(Introsort) 하이브리드 알고리즘이다.
C++ sort() - 한 줄이면 끝
| 데이터 크기 | 사용 알고리즘 | 이유 |
| ~16개 이하 | 삽입 정렬 | 작은 데이터에서 빠름 |
| 일반적인 경우 | 퀵 정렬 | 평균 O(n log n), 캐시 친화 |
| 최악 감지 시 | 힙 정렬로 전환 | O(n^2) 방지 |
※ sort()는 "상황에 맞는 도구를 고르는" 똑똑한 함수다.
CS 돋보기 - 분할 정복과 CPU의 비교 연산
분할 정복의 3단계 - "혼자 다 하지 마라"
CS에서 가장 중요한 문제 해결 패러다임이다.
: 후자가 관리하기 쉬움
분할 정복 - "언제 멈추는 가?"
계속 쪼개면 결국 더 나눌 수 없는 지점에 도달한다. 그 지점이 Base Case.
Base Case = 재귀의 종료 조건
ex1) 병합 정렬: 원소 1개만 남으면 멈춤(Base Case) → 1개짜리는 이미 정렬됨
ex2) 이진 탐색: 범위 1칸이면 멈춤 (Base Case) → 찾았거나, 없거나
CPU의 비교 연산 - "진짜 하는 일"
if (a > b) 한 줄이 CPU에서는 어떻게 실행되는가?
1. a - b 계산 (뺄셈)
2. 결과가 양수/음수/0인지 → 플래그 레지스터에 기록
3. CPU 클럭 1~수 사이클에 완료
※ CPU는 "1초에 약 1억번"연산하므로 O(n log n)기준 100만개도 0.2초에 끝난다.
분할 정복이 쓰이는 곳들
- 병합 정렬 - 오늘 배운 것
- 이진 탐색 - 정렬된 배열을 반으로 나누며 찾기
- 쿼리 옵티마이저 - 데이터베이스가 큰 테이블을 분할 처리
- MapReduce - 구글이 빅데이터를 처리하는 방식(분할 정복의 대규모 버전)
- FFT / Strassen 행렬 곱셈 - 신호 처리, 수치 계산
※ "큰 문제를 작은 문제로 쪼개서 해결한다."
: CS 전체를 관통하는 보편 전략
실제 사용 예
게임 개발
렌더링: 화면에 그리는 순서를 정한다.
3D 게임에서부터 투명한 오브젝트는 카메라로부터 거리순으로 정렬해서 뒤에서부터 그려야한다. (Painter's Algorithm)
매 프레임 수천 개의 오브젝트를 정렬 →
O(n^2)이면 프레임 드랍, O(n log n)이어야 60FPS 유지
UE5의 TArray::Sort()도 내부적으로 인트로소트 사용
웹/서버
쇼핑몰의 "가격순", "인기순", "최신순" 버튼 - 누를 때마다 서버에서 정렬이 실행된다.
O(n^2) 정렬: 수십 초
O(n log n) 정렬: 1초 이내
실제로는 DB의 인덱스(B-Tree)로 미리 정렬된 상태를 유지한다.
대신 삽입할 때 추가 비용이 드는 양자택일이 있음.
CS 전반
정렬은 CS에서 가장 많이 연구된 문제이다.
O(n log)은 비교 기반 정렬의 이론적 하한 - 수학적으로 증명됨. 비교만으로는 이보다 빠를 수 없음.
단, 비교하지 않는 정렬은 O(n)이 가능하다 (예: 카운팅 정렬, 기수 정렬)
"문제의 제약을 바꾸면 한계를 돌파할 수 있다."
: 분할 정복은 정렬 뿐 아니라 FFT, Strassen 행렬 곱셈 등 CS 곳곳에 등장하는 보편 패러다임
오늘의 핵심
정렬의 본질은 "비교하고 교환하기"
: 버블(인접 비교), 선택(최솟값), 삽입(끼워넣기) - 모두 O(n^2)
O(n^2) vs O(n log n)은 압도적 차이
: 100만개 기준 3시간 vs 0.2초 - "어떻게 정렬하느냐"가 만드는 100만배의 차이
분할 정복이 빠른 정렬의 비밀
: 큰 문제를 쪼개서 풀면 n^2 → n log n. 병합 정렬이 대표적인 예.
C++ sort()는 이미 최적화된 도구
: 퀵+삽입+힙 하이브리드(인트로소트). 원리를 알면 자신 있게 쓴다.
정렬된 데이터는 강력하다.
: 정렬 후에는 탐색이 빨라진다.
댓글
댓글 쓰기