다음 파이썬 코드로 작성된 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번
제시 partition을 실제로 추적하면 첫 전체 분할 뒤 7,3,2,11,13,5,17,19, 다음 부분 분할 뒤 2,3,5,11,13,7,17,19, 이후 2,3,5,7,13,11,17,19가 나타난다. 2,3,5,11,7,13,17,19는 어느 swap 또는 pivot 배치 직후에도 나타나지 않으므로 ②가 정답이다.
콘텐츠 정보
- 자료 유형
- 공개 기출
- 검수 상태
- 내용 검수 완료
- 해설 작성·검수
- 정처LAB 편집 기준
- 최종 검수
- 2026-09-05