다음 알고리즘에 해당하는 정렬은?sort(arr[], n){ // ar… | [7급 국가직 알고리즘] 23년 1회차 기출문제 상세 페이지
1[7급 국가직 알고리즘] 23년 1회차
다음 알고리즘에 해당하는 정렬은?sort(arr[], n){ // arr 배열의 인덱스는 0 ～ n-1
for i ← 1 to n - 1 {
cur ← arr[i];
j ← i – 1;
while (j ≧ 0) and (arr[j] > cur) {
arr[j + 1] ← arr[j];
j ← j – 1;
}
arr[j + 1] ← cur;
}
}1
쉘(shell) 정렬
2
기수(radix) 정렬
3
선택(selection) 정렬
4
삽입(insertion) 정렬
해설
제시된 코드는 삽입(insertion) 정렬이다.
i번째 원소를 cur에 두고, 앞쪽의 이미 정렬된 구간에서 cur보다 큰 원소를 한 칸씩 오른쪽으로 밀어낸 뒤 빈자리에 cur을 끼워 넣는 구조다.
- 쉘 정렬은 일정 간격(gap)으로 떨어진 원소끼리 삽입 정렬을 하고 간격을 줄여 가는데, 이 코드는 간격 없이 인접 원소만 비교한다.
- 기수 정렬은 자릿수별로 버킷에 분배하는 비교 없는 정렬이지만, 이 코드는 원소끼리 대소를 비교한다.
- 선택 정렬은 남은 구간의 최솟값을 찾아 교환하는 방식이라, 원소를 밀어 옮기는 이 코드와 다르다.
오류나 개정된 내용이 보이면 알려주세요