다음 표는 버블 정렬과 선택 정렬을 나란히 비교한 것이다.
▼ 표 5-2
|
원소 개수(N) |
버블 정렬에서 최대 단계 수 |
선택 정렬에서 최대 단계 수 |
|
5 |
52 / 2 =12.5 |
14(10번의 비교 + 4번의 교환) |
|
10 |
102 / 2 =50 |
54(45번의 비교 + 9번의 교환) |
|
20 |
202 / 2 200 |
199(180번의 비교 + 19번의 교환) |
|
40 |
402 / 2 = 800 |
819(780번의 비교 + 39번의 교환) |
|
80 |
802 / 2 = 3239 |
3239(3160번의 비교 + 79번의 교환) |
표에서 비교한 바에 따르면 선택 정렬은 분명 버블 정렬보다 단계 수가 반 정도 적다. 즉, 선택 정렬이 두 배 더 빠르다.