배열 A = [5, 2, 4, 6, 1, 3]를 삽입 정렬로 오름차순 … | [7급 국가직 알고리즘] 26년 1회차 기출문제 상세 페이지

1[7급 국가직 알고리즘] 26년 1회차

배열 A = [5, 2, 4, 6, 1, 3]를 삽입 정렬로 오름차순 정렬할 때, 전체 과정에서 수행되는 key 값의 총 비교 횟수는? (단, 알고리즘은 다음과 같이 동작한다고 가정하며, 배열의 인덱스는 1부터 시작하고, n 값은 배열 A의 원소의 개수이다)
for i ← 2 to n do
    key ← A[i]
    j ← i - 1
    while j ≥ 1 and A[j] > key do
        A[j+1] ← A[j]
        j ← j - 1
    A[j+1] ← key

해설

key 값의 총 비교 횟수는 12회이다.
비교는 while 조건의 A[j] > key 가 평가될 때마다 1회이며, j가 0이 되면 비교 없이 종료된다.
i=2(key 2): 5와 비교 → 1회, [2,5,4,6,1,3]
i=3(key 4): 5, 2와 비교 → 2회, [2,4,5,6,1,3]
i=4(key 6): 5와 비교 → 1회
i=5(key 1): 6, 5, 4, 2와 비교 후 j=0 → 4회, [1,2,4,5,6,3]
i=6(key 3): 6, 5, 4, 2와 비교 → 4회
합계: 1 + 2 + 1 + 4 + 4 = 12

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기

[7급 국가직 알고리즘] 26년 1회차 25문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요

비슷한 기출

7급 국가직 알고리즘 기출문제 암기장 전체 보기

💬 자격증 스터디 커뮤니티헷갈리는 문제, 같이 준비하는 사람들에게 물어보세요

→