개념과 작동 원리
정렬은 주어진 순서 기준에 맞게 데이터를 재배치하는 과정입니다. 버블 정렬은 이웃을 비교하고 병합 정렬은 나눈 목록을 합치는 구조를 사용합니다.
알고리즘의 반복 구조는 입력 크기가 늘 때 작업량이 얼마나 커지는지 결정합니다. 같은 크기라도 초기 순서와 구현의 종료 조건이 결과를 바꿀 수 있습니다.
관계식과 성립 조건
전형적인 버블 정렬의 비교량은 n² 규모, 병합 정렬은 n log n 규모입니다. 특정 비교 횟수와 점근적 표기 O는 같은 정보가 아닙니다.
실험은 값 비교·교환·쓰기를 세며 컴퓨터의 실제 시간을 재는 벤치마크가 아닙니다. 병합의 데이터 쓰기와 자리 교환도 같은 연산으로 섞지 않습니다.
가상 실험에서 읽을 변화
비교 횟수는 데이터 수와 초기 순서, 알고리즘에 따라 달라져요.
실행 시간 대신 값 비교와 자리 교환을 세어요. 병합 정렬의 쓰기는 교환과 구분해요.
핵심 관계와 기호
bubble: n(n−1)/2 · merge: O(n log₂n)
| 기호 | 뜻 | 단위 |
|---|---|---|
| n | 입력 데이터 개수 | 개 |
| O(n log n) | 입력 크기에 따른 점근적 증가의 상한 표현 | 복잡도 |
예시로 확인하기
병합 정렬의 쓰기와 교환은 같은 연산인가요?
다른 연산이에요 · 비교 횟수는 데이터 수와 초기 순서, 알고리즘에 따라 달라져요.
자주 헷갈리는 점
- 비교 횟수가 작다는 사실만으로 모든 컴퓨터와 입력에서 실제 시간이 같은 비율로 짧아지는 것은 아닙니다.