다음 파이썬 프로그램의 실행 결과는?a=[29,88,60,26,40,7… | [7급 국가직 알고리즘] 24년 1회차 기출문제 상세 페이지
1[7급 국가직 알고리즘] 24년 1회차
다음 파이썬 프로그램의 실행 결과는?a=[29,88,60,26,40,74,43,22,61,40]
def partition():
i = -1
n = len(a)
for j in range(0, n-2):
if a[j] <= a[n-1]:
i += 1
b = a[i]
a[i] = a[j]
a[j] = b
b = a[i+1]
a[i+1] = a[n-1]
a[n-1] = b
partition()
print(a)
1
29 22 26 40 40 74 43 88 61 60
2
29 22 40 26 40 74 43 88 61 60
3
29 26 22 40 40 74 43 60 61 88
4
29 26 40 22 40 74 43 88 61 60
해설
실행 결과는 29 26 40 22 40 74 43 88 61 60이다.
마지막 원소 a[9]=40을 피벗으로 삼아 피벗 이하인 원소를 앞쪽으로 교환하는 로무토 분할이다. 단, 반복이 range(0, n-2)이므로 j=0~7만 검사한다.
j=0: 29 ≤ 40 → i=0, 제자리
j=3: 26 → i=1, a[1]과 교환 → 29 26 60 88 40 …
j=4: 40 → i=2, a[2]와 교환 → 29 26 40 88 60 …
j=7: 22 → i=3, a[3]과 교환 → 29 26 40 22 60 74 43 88 61 40
끝으로 a[4]와 a[9] 교환 → 29 26 40 22 40 74 43 88 61 60
- 29 22 26 40 40 74 43 88 61 60은 교환이 일어난 순서(26 → 40 → 22)를 무시하고 앞부분을 다르게 배치한 결과이다.
- 29 22 40 26 40 74 43 88 61 60은 22가 26보다 앞에 있어, 26이 먼저 a[1]로 교환되는 진행과 맞지 않는다.
- 29 26 22 40 40 74 43 60 61 88은 22와 40의 순서가 바뀌었고, 마지막 교환으로 a[4]의 60이 맨 끝에 와야 하는데 88이 와 있다.
오류나 개정된 내용이 보이면 알려주세요