🧠 목차
1. 정렬 알고리즘
이번 챕터에서 다룰 정렬 알고리즘의 정의
- 버블 정렬: 데이터의 인접한 요소끼리 비교하고, swap 연산을 수행하며 정렬하는 방식
- 선택 정렬: 대상에서 가장 크거나 작은 데이터를 찾아가 선택을 반복하면서 정렬하는 방식
- 삽입 정렬: 대상을 선택해 정렬된 영역에서 선택 데이터의 적절한 위치를 찾아 삽입하면서 정렬하는 방식
- 퀵 정렬: pivot 값을 선정해 해당 값을 기준으로 정렬하는 방식
- 병합 정렬: 이미 정렬된 부분 집합들을 효율적으로 병합해 전체를 정렬하는 방식
- 기수 정렬: 데이터의 자릿수를 바탕으로 비교해 데이터를 정렬하는 방식
| 정렬 알고리즘 | 시간 복잡도 (최선 ~ 최악) | 공간 복잡도 | 안정 정렬 여부 | 사용 예 |
| 버블 정렬 | O(n²) | O(1) | ✅ | 거의 정렬된 데이터, 교육용 |
| 선택 정렬 | O(n²) | O(1) | ❌ | 메모리 제한 환경, 단순 비교 |
| 삽입 정렬 | O(n) ~ O(n²) | O(1) | ✅ | 작은 데이터 집합, 거의 정렬된 배열 |
| 퀵 정렬 | O(n log n) ~ O(n²) | O(log n) | ❌ | 일반적인 대용량 정렬, 내부 정렬 |
| 병합 정렬 | O(n log n) | O(n) | ✅ | 안정성이 필요한 경우, 외부 정렬 |
| 기수 정렬 | O(nk) | O(n + k) | ✅ | 자릿수가 있는 정수(전화번호, 주민번호 등) |
2. 버블 정렬
버블 정렬 (bubble sort)
- 인접한 데이터의 크기를 비교해 정렬하는 방법
- 루프를 돌면서 인접한 데이터 간의 swap 연산으로 정렬한다.
- 간단하게 구현 가능
- 시간 복잡도 O(n²), 다른 정렬 알고리즘보다 느린편이다.
버블 정렬 과정
- 비교 연산이 필요한 루프 범위를 설정한다.
- 인접한 데이터 값을 비교한다.
- swap 조건에 부합하면 swap 연산을 수행한다.
- 루프 범위가 끝날 때까지 2~3을 반복한다.
- 정렬 영역을 설정한다. 다음 루프를 실행할 때는 이 영역을 제외한다.
- 비교 대상이 없을 때까지 1~5를 반복한다.
문제는 내일 !
3. [실전 문제] 수 정렬하기 (백준 2750)
'알고리즘 & 코딩 테스트 이론 > 강의' 카테고리의 다른 글
| [🧠 Do it! 알고리즘] 2-5. 스택과 큐 (0) | 2025.05.06 |
|---|---|
| [🧠 Do it! 알고리즘] 2-4. 슬라이딩 윈도우(Sliding Window) (1) | 2025.05.05 |
| [🧠 Do it! 알고리즘] 2-3. 투 포인터 (0) | 2025.05.04 |
| [🧠 Do it! 알고리즘] 2-2. 구간 합 (1) | 2025.05.03 |
| [🧠 Do it! 알고리즘] 2-1. 배열과 리스트 (1) | 2025.05.02 |