각각 1,000 개의 데이터로 이루어진 데이터 세트 ‘A’와 ‘B’에 … | [7급 국가직 자료구조론] 08년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 08년 1회차
각각 1,000 개의 데이터로 이루어진 데이터 세트 ‘A’와 ‘B’에 대해 ‘갑’과 ‘을’의 두 가지 정렬 기법으로 정렬을 수행했을 때 다음과 같은 시간이 소요되었다.
| 정렬 기법 데이터 세트 | 갑 | 을 |
|---|---|---|
| A | 0.21초 | 0.40초 |
| B | 6.71초 | 0.39초 |
갑 을
1
퀵 정렬 합병 정렬
2
힙 정렬 퀵 정렬
3
합병 정렬 퀵 정렬
4
합병 정렬 힙 정렬
해설
갑은 퀵 정렬, 을은 합병 정렬이다.
갑은 데이터 세트 B에서 시간이 30배 이상 늘었다. 데이터 분포(이미 정렬된 경우 등)에 따라 최악 로 떨어지는 기법은 퀵 정렬뿐이다.
을은 두 세트에서 시간이 거의 같으므로 분포와 무관하게 인 기법이며, 갑이 퀵 정렬인 조합은 을이 합병 정렬인 경우뿐이다.
- 힙 정렬과 퀵 정렬: 힙 정렬은 입력 분포와 무관하게 이라 갑처럼 급격히 느려지지 않는다.
- 합병 정렬과 퀵 정렬: 합병 정렬도 최악이 이라 갑의 큰 편차를 설명하지 못한다.
- 합병 정렬과 힙 정렬: 둘 다 분포에 둔감해 갑의 큰 편차가 나올 수 없다.
오류나 개정된 내용이 보이면 알려주세요