다음 배열 데이터에서 첫 번째 원소 ‘66’을 피봇(pivot)으로 퀵… | [7급 국가직 자료구조론] 15년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 15년 1회차
다음 배열 데이터에서 첫 번째 원소 ‘66’을 피봇(pivot)으로 퀵정렬(Quick Sort)을 수행하는 경우, 순환 함수 quickSort()의 첫 번째 라운드가 완료되었을 때 생성된 배열 상태로 옳은 것은? (단, 퀵정렬 함수는 quickSort(int a[ ], int left, int right)이고, 매개변수 left와 right는 배열 a에서 정렬할 시작 위치와 끝 위치를 나타낸다)int a[ ] = { 66, 51, 11, 98, 55, 1, 70, 35, 79, 41 };
1
11, 51, 35, 41, 55, 1, 66, 70, 79, 98
2
35, 51, 11, 41, 55, 1, 66, 70, 79, 98
3
55, 79, 70, 98, 66, 1, 11, 35, 51, 41
4
66, 79, 70, 98, 55, 1, 11, 35, 51, 41
해설
첫 라운드 후 배열은 35, 51, 11, 41, 55, 1, 66, 70, 79, 98이다.
왼쪽에서는 피봇보다 큰 값, 오른쪽에서는 피봇보다 작은 값을 찾아 교환한다. 98과 41, 70과 35를 교환한 뒤 두 포인터가 교차하면 피봇 66을 교차 위치의 35와 맞바꾼다.
그 결과 66 왼쪽에는 작은 값, 오른쪽에는 큰 값만 남아 피봇이 최종 위치에 고정된다.
- 11, 51, 35, 41, …로 시작하는 배열: 피봇과 맞바뀌는 값은 교차 위치의 35이므로 맨 앞이 11이 될 수 없다.
- 55, 79, 70, 98, 66, …: 66 왼쪽에 79·70·98 같은 큰 값이 있어 분할 조건에 어긋난다.
- 66, 79, 70, 98, 55, …: 피봇이 맨 앞에 그대로 있어 분할이 완료되지 않은 상태이다.
오류나 개정된 내용이 보이면 알려주세요