문제 18정답을 고른 뒤 해설을 펼쳐보세요.
다음 파이썬 코드로 작성된 partition() 함수를 이용하여, 주어진 배열을 퀵 정렬(quick sort)로 오름차순 정렬하고자 한다. 정렬 과정에서 단계별 정렬 순서로 나타날 수 없는 것은? (단, 피벗(pivot)은 정렬하고자 하는 대상의 마지막 원소로 선택한다)
# 정렬하고자 하는 대상인 A[first]…A[last]를
# 피벗(A[last]) 기준으로 분할하는 함수
def partition(A, first, last):
p = A[last]
low = first
high = last
while low < high:
while p > A[low] and low < high:
low += 1
while p <= A[high] and low < high:
high -= 1
if low < high:
A[low], A[high] = A[high], A[low]
A[low], A[last] = A[last], A[low]
return low
배열 7 3 2 19 13 5 11 17
- ①2, 3, 5, 7, 13, 11, 17, 19정답
- ②2, 3, 5, 11, 7, 13, 17, 19정답
- ③2, 3, 5, 11, 13, 7, 17, 19정답
- ④7, 3, 2, 11, 13, 5, 17, 19정답
정답·해설 펼치기정답·해설 접기
정답: 공식 최종정답 기준 · 검수 방식
정답 근거
정답은 ②입니다. 처음 피벗 17로 분할하면 19와 11이 교환되고, 마지막에 19와 17이 교환되어 [7, 3, 2, 11, 13, 5, 17, 19]가 됩니다(④). 왼쪽 부분 [7, 3, 2, 11, 13, 5]를 피벗 5로 분할하면 7과 2가 교환되고 7과 5가 교환되어 [2, 3, 5, 11, 13, 7, 17, 19]가 됩니다(③). 이어 [11, 13, 7]을 피벗 7로 분할하면 11과 7이 교환되어 [2, 3, 5, 7, 13, 11, 17, 19]가 됩니다(①). 마지막으로 [13, 11]이 정렬됩니다.
보기별 검토
① 세 번째 분할 결과로 나타납니다.
② 7이 11과 13 사이에 오는 상태는 어느 분할 단계에서도 나오지 않으므로 정답입니다.
③ 두 번째 분할 결과로 나타납니다.
④ 첫 번째 분할 결과로 나타납니다.
풀이 요령 · 관련 개념
풀이 요령: 퀵 정렬에서는 한 번 분할이 끝날 때마다 피벗이 최종 위치에 고정됩니다. 각 선지에서 「이미 고정되어야 할 원소」가 제자리에 있는지 확인하면 빠르게 걸러낼 수 있습니다.