정렬과 탐색 알고리즘
정렬 = 데이터를 쓸모있게 만드는 첫 번째 단계
정렬 알고리즘
O(n²) 계열 — 단순하지만 느림
| 이름 | 방식 | 특징 |
|---|---|---|
| 버블 정렬 | 인접한 두 수 비교, 큰 수를 오른쪽으로 | 가장 직관적. 큰 값이 거품처럼 오른쪽으로 떠오름 |
| 선택 정렬 | 남은 것 중 최솟값 찾아 맨 앞에 배치 | 매번 전체를 훑으며 최솟값 선택 |
| 삽입 정렬 | 정렬된 영역에 새 값을 알맞은 위치에 끼워넣기 | 카드를 한 장씩 받아 손패를 정리하는 느낌 |
O(n log n) 계열 — 실무에서 쓰이는 정렬
| 이름 | 방식 | 특징 |
|---|---|---|
| 퀵 정렬 | 피벗 기준으로 작은 건 왼쪽, 큰 건 오른쪽 | 평균 최강. Dart sort()도 이 계열. 분할 정복 |
| 머지 정렬 | 반으로 쪼개고 정렬하면서 합침 | 최악도 O(n log n). 순서 안정적. 추가 메모리 필요 |
| 힙 정렬 | 힙 자료구조 활용 | 추가 메모리 없이 O(n log n) |
| 기수 정렬 | 자릿수별로 정렬 | 비교 없이 정렬, 특수 케이스에서 빠름 |
| 팀 정렬 | 삽입 + 머지 혼합 | Python, Java 기본 정렬. 현실 데이터에 최적화 |
앱에서 정렬은 어디에?
- 쇼핑앱 — 가격순, 인기순, 최신순, 할인율순
- 채팅앱 — 최근 메시지순, 읽지 않은 순
- 할일앱 — 우선순위순, 마감일순
- 지도앱 — 거리 가까운 순, 평점 높은 순
- 음악앱 — 최신순, 인기순
- 검색앱 — 관련도순, 최신순
탐색 알고리즘
선형 탐색 O(n)
- 처음부터 하나씩 확인
- 정렬 불필요, 구현 단순
- 데이터 많으면 느림
이진 탐색 O(log n)
- 반씩 나눠서 범위를 좁혀감
- 정렬 필수
- 데이터 많을수록 선형 대비 압도적으로 빠름
해시 탐색 O(1)
- 키를 넣으면 값의 위치를 바로 계산
- Dart의
Map,Set이 해시 기반 - 해시 함수 품질이 성능 핵심
DFS — 깊이 우선 탐색
- 한 방향으로 끝까지 간 뒤 되돌아옴
- 스택(재귀) 사용
- 경로 탐색, 미로 풀기에 적합
BFS — 너비 우선 탐색
- 가까운 노드부터 넓게 탐색
- 큐 사용
- 최단 경로 탐색에 적합
느낀 점
정렬은 거의 라이브러리가 해주지만 어떤 기준으로 정렬할지는 개발자 몫.
탐색은 자료구조 선택이 성능을 결정함. 빠른 조회가 필요하면 Map(해시)부터 고려하기.
