다음 자료에서 첫 행은 오름차순으로 정렬하기 위해 주어진 입력 값이고 … | [7급 국가직 자료구조론] 17년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 17년 1회차
다음 자료에서 첫 행은 오름차순으로 정렬하기 위해 주어진 입력 값이고 마지막 행은 정렬이 완료된 후의 결과이다. 중간의 행들은 합병정렬(merge sort), 삽입정렬(insertion sort), 선택정렬(selection sort), 퀵정렬(quick sort) 알고리즘을 통하여 얻을 수 있는 중간 과정을 보여준다. 각 행에 사용된 정렬 알고리즘을 바르게 나열한 것은? (단, 퀵정렬에서 피봇은 가장 오른쪽에 있는 원소를 사용한다)
| 입력 | 21 | 41 | 15 | 25 | 21 | 37 | 45 | 9 | 23 | 18 | 36 | 4 | 11 |
| ㉠ | 9 | 15 | 21 | 21 | 25 | 37 | 41 | 45 | 23 | 18 | 36 | 4 | 11 |
| ㉡ | 4 | 9 | 11 | 15 | 18 | 37 | 45 | 41 | 23 | 21 | 36 | 21 | 25 |
| ㉢ | 15 | 21 | 21 | 25 | 37 | 41 | 45 | 9 | 18 | 23 | 4 | 11 | 36 |
| ㉣ | 4 | 9 | 11 | 25 | 21 | 37 | 45 | 41 | 23 | 18 | 36 | 21 | 15 |
| 결과 | 4 | 9 | 11 | 15 | 18 | 21 | 21 | 23 | 25 | 36 | 37 | 41 | 45 |
1
삽입정렬 선택정렬 합병정렬 퀵정렬
2
삽입정렬 퀵정렬 합병정렬 선택정렬
3
합병정렬 선택정렬 삽입정렬 퀵정렬
4
합병정렬 퀵정렬 선택정렬 삽입정렬
해설
각 행은 차례로 삽입정렬, 선택정렬, 합병정렬, 퀵정렬의 중간 과정이다.
㉠은 앞의 8개만 정렬되어 있고 나머지는 입력 순서 그대로여서 정렬 구간을 하나씩 넓혀 가는 삽입정렬이다. ㉢은 정렬된 구간 3개(15~45의 7개, 9·18·23, 4·11·36)로 나뉘어 있어 부분 리스트를 정렬한 뒤 합치는 합병정렬이다.
㉡과 ㉣은 모두 최솟값을 앞으로 교환하는 선택정렬로 만들 수 있지만, ㉣은 맨 오른쪽 11을 피봇으로 분할한 결과(11 왼쪽에 4·9, 오른쪽에 더 큰 값)와도 같다. ㉡은 퀵정렬로 만들 수 없으므로 ㉡이 선택정렬, ㉣이 퀵정렬이다.
- ㉡을 퀵정렬로 보는 나열: 18이 제자리에 오려면 그보다 먼저 남은 구간의 피봇 25가 제자리로 옮겨져야 하는데 ㉡에서는 25가 맨 끝에 남아 있다.
- ㉠을 합병정렬로 보는 나열: 앞 8개만 정렬되고 나머지가 입력 그대로인 형태는 합병정렬의 분할·병합으로 나오지 않는다.
- ㉢을 삽입정렬로 보는 나열: 뒤쪽 원소 9·18·23과 4·11·36이 입력과 다른 순서로 각각 정렬되어 있어 삽입정렬의 중간 결과가 아니다.
오류나 개정된 내용이 보이면 알려주세요