다음 C언어 함수 ABC()에 대한 설명으로 옳은 것은?void ABC… | [7급 국가직 알고리즘] 25년 1회차 기출문제 상세 페이지

다음 C언어 함수 ABC()에 대한 설명으로 옳은 것은?
void ABC(int A[], int n) {
    int i, j, tmp;
    for(i = n - 1; i > 0; i--) {
        j = 0;
        while(j < i) {
            if(A[j] < A[j + 1]) {
                tmp = A[j];
                A[j] = A[j + 1];
                A[j + 1] = tmp;
            }
            j = j + 1;
        }
    }
}

코드 수행 완료 후, A[0]에는 가장 큰 원소가 저장되어 있다.

코드 수행 완료 후, 배열 A의 원소는 오름차순으로 정렬되어 있다.

최선의 경우와 최악의 경우의 수행 시간 복잡도가 다르다.

코드는 삽입 정렬(insertion sort)을 구현한 것이다.

함수 실행이 끝나면 A[0]에 가장 큰 원소가 저장된다.
인접한 두 원소를 비교해 앞의 값이 더 작으면 교환하는 버블 정렬로, 매 반복마다 가장 작은 값이 뒤로 밀려나 배열이 내림차순으로 정렬된다.
작은 값이 뒤로 가도록 교환하므로 결과는 오름차순이 아니라 내림차순이다.
교환이 없어도 조기 종료하는 장치가 없어 비교 횟수가 항상 같으므로, 최선과 최악 모두 $\mathrm{O}(n^2)$로 같다.
인접 원소를 비교·교환하는 방식은 삽입 정렬이 아니라 버블 정렬이다.