다음 데이터를 퀵정렬(quick sort)하려고 한다. 퀵정렬 1단계 … | [7급 국가직 자료구조론] 09년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 09년 1회차
다음 데이터를 퀵정렬(quick sort)하려고 한다. 퀵정렬 1단계 과정이 끝난 후, 피봇키(pivot key)를 중심으로 좌측에는 피봇키보다 작은 수, 우측에는 피봇키보다 큰 수들로 데이터가 분할된 상태를 올바르게 나타낸 것은? (단, 피봇키는 가장 왼쪽에 있는 값으로 한다)(초기데이터)
[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] 8 1 4 9 6 3 5 2 7 0
(보기의 인덱스: [0] [1] [2] [3] [4] [5] [6] [7] [8] [9])
1
7 1 4 6 3 5 2 0 8 9
2
7 1 4 0 6 3 5 2 8 9
3
2 1 4 0 6 3 5 7 8 9
4
0 1 4 2 6 3 5 7 8 9
해설
1단계 분할 결과는 7 1 4 0 6 3 5 2 8 9이다.
피봇 8을 두고 왼쪽 포인터 i는 8보다 큰 값, 오른쪽 포인터 j는 8보다 작은 값을 찾아 교환한다.
i는 9([3]), j는 0([9])에서 멈춰 교환 → 8 1 4 0 6 3 5 2 7 9
다시 i는 9([9]), j는 7([8])에서 멈추고 두 포인터가 엇갈린다.
마지막으로 피봇과 j 위치의 7을 교환 → 7 1 4 0 6 3 5 2 8 9
- 7 1 4 6 3 5 2 0 8 9: 9와 0의 교환이 반영되지 않아 0이 [3]에 오지 않았다.
- 2 1 4 0 6 3 5 7 8 9: 피봇은 j 위치의 7과 교환되므로 [0]에는 7, [7]에는 2가 그대로 있어야 한다.
- 0 1 4 2 6 3 5 7 8 9: [0]에는 7, [3]에는 0, [7]에는 2가 와야 하므로 교환 결과와 맞지 않는다.
오류나 개정된 내용이 보이면 알려주세요