다음 파이썬 코드로 작성된 partition() 함수를 이용하여, 주어… | [9급 국가직 컴퓨터일반] 26년 1회차 기출문제 상세 페이지

다음 파이썬 코드로 작성된 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

주어진 partition()으로 정렬하면 2, 3, 5, 11, 7, 13, 17, 19는 나타나지 않는다.
단계별 추적(피벗은 각 구간의 마지막 원소):
구간 [0~7], 피벗 17: 7, 3, 2, 11, 13, 5, 17, 19
구간 [0~5], 피벗 5: 2, 3, 5, 11, 13, 7, 17, 19
구간 [0~1], 피벗 3: 변화 없음
구간 [3~5], 피벗 7: 2, 3, 5, 7, 13, 11, 17, 19
구간 [4~5], 피벗 11: 2, 3, 5, 7, 11, 13, 17, 19
구간 [3~5]에서 피벗 7이 맨 앞 11과 자리를 바꾸므로 11, 7, 13 배치는 어느 단계에서도 생기지 않는다.
7, 3, 2, 11, 13, 5, 17, 19: 피벗 17로 처음 분할한 결과이다.
2, 3, 5, 11, 13, 7, 17, 19: 피벗 5로 왼쪽 구간을 분할한 결과이다.
2, 3, 5, 7, 13, 11, 17, 19: 피벗 7로 구간 [3~5]를 분할한 결과이다.