배열 A를 오름차순으로 정렬하기 위해 5, 3, 1의 간격을 사용하여 … | [7급 국가직 알고리즘] 24년 1회차 기출문제 상세 페이지
1[7급 국가직 알고리즘] 24년 1회차
배열 A를 오름차순으로 정렬하기 위해 5, 3, 1의 간격을 사용하여 셸(Shell) 정렬을 수행할 때, 간격 3에 대한 처리까지 수행을 완료한 후의 배열 A의 상태로 옳은 것은?
i 0 1 2 3 4 5 6 7 8 9 10 A[i] 9 18 26 21 4 17 13 2 6 24 8
1
4 9 13 26 6 8 18 24 2 17 21
2
6 4 2 8 13 9 18 17 21 24 26
3
9 2 6 13 4 17 21 8 26 24 18
4
9 18 26 4 17 21 2 6 13 8 24
해설
간격 3까지 처리한 배열은 6 4 2 8 13 9 18 17 21 24 26이다.
셸 정렬은 간격 h만큼 떨어진 원소끼리 부분 배열을 만들어 각각 삽입 정렬한다.
간격 5: (9, 17, 8) → (8, 9, 17), (18, 13) → (13, 18), (26, 2) → (2, 26), (21, 6) → (6, 21), (4, 24) 유지
→ 8 13 2 6 4 9 18 26 21 24 17간격 3: 인덱스 0·3·6·9의 (8, 6, 18, 24) → (6, 8, 18, 24), 인덱스 1·4·7·10의 (13, 4, 26, 17) → (4, 13, 17, 26), 인덱스 2·5·8의 (2, 9, 21) 유지
→ 6 4 2 8 13 9 18 17 21 24 26
- 4 9 13 26 6 8 18 24 2 17 21은 간격 3 부분 배열의 정렬 결과와 맞지 않는다. 인덱스 0에는 해당 그룹의 최솟값 6이 와야 한다.
- 9 2 6 13 4 17 21 8 26 24 18은 간격 5 처리를 건너뛰고 원래 배열에 간격 3만 적용한 결과이다.
- 9 18 26 4 17 21 2 6 13 8 24는 간격으로 떨어진 원소가 아니라 이웃한 세 원소씩 묶어 정렬한 결과이다.
오류나 개정된 내용이 보이면 알려주세요