다음과 같이 배열에 저장된 입력 자료들을 퀵 정렬(quick sort)… | [7급 국가직 자료구조론] 19년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 19년 1회차
다음과 같이 배열에 저장된 입력 자료들을 퀵 정렬(quick sort)로 오름차순 정렬하고자 한다. 정렬과정에서 단계별 정렬 순서로 나타날 수 없는 것은? (단, 피봇(pivot)은 마지막 레코드로 선택한다)
| 15 | 3 | 1 | 35 | 20 | 4 | 18 | 26 |
1
15, 3, 1, 18, 20, 4, 26, 35
2
15, 3, 1, 4, 20, 18, 26, 35
3
1, 3, 4, 18, 20, 15, 26, 35
4
1, 3, 4, 15, 20, 18, 26, 35
해설
마지막 레코드를 피봇으로 분할해 가면 15, 3, 1, 4, 20, 18, 26, 35는 어느 단계에서도 나타나지 않는다.
1단계(피봇 26): 왼쪽에서 26 이상인 35, 오른쪽에서 26 미만인 18을 찾아 교환한 뒤, 엇갈린 위치에 피봇을 놓으면 15, 3, 1, 18, 20, 4, 26, 35가 된다.
2단계(왼쪽 구간, 피봇 4): 15와 1을 교환하고 피봇을 놓아 1, 3, 4, 18, 20, 15, 26, 35가 된다.
3단계(18, 20, 15 구간, 피봇 15): 1, 3, 4, 15, 20, 18, 26, 35가 된다.1단계 직후 피봇 왼쪽 구간의 다음 피봇은 4이므로, 15, 3, 1이 앞에 그대로 남은 채 4와 18의 자리만 바뀐 배열은 분할 과정에서 만들어지지 않는다.
- 15, 3, 1, 18, 20, 4, 26, 35는 1단계 결과이다.
- 1, 3, 4, 18, 20, 15, 26, 35는 2단계 결과이다.
- 1, 3, 4, 15, 20, 18, 26, 35는 3단계 결과이다.
오류나 개정된 내용이 보이면 알려주세요