다음 자료에서 첫 행은 오름차순으로 정렬하기 위해 주어진 입력 값이고 … | [7급 국가직 자료구조론] 17년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 17년 1회차
다음 자료에서 첫 행은 오름차순으로 정렬하기 위해 주어진 입력 값이고 마지막 행은 정렬이 완료된 후의 결과이다. 중간의 행들은 합병정렬(merge sort), 삽입정렬(insertion sort), 선택정렬(selection sort), 퀵정렬(quick sort) 알고리즘을 통하여 얻을 수 있는 중간 과정을 보여준다. 각 행에 사용된 정렬 알고리즘을 바르게 나열한 것은? (단, 퀵정렬에서 피봇은 가장 오른쪽에 있는 원소를 사용한다)
입력214115252137459231836411
㉠915212125374145231836411
㉡491115183745412321362125
㉢152121253741459182341136
㉣491125213745412318362115
결과491115182121232536374145
㉠ ㉡ ㉢ ㉣
1
삽입정렬 선택정렬 합병정렬 퀵정렬
2
삽입정렬 퀵정렬 합병정렬 선택정렬
3
합병정렬 선택정렬 삽입정렬 퀵정렬
4
합병정렬 퀵정렬 선택정렬 삽입정렬
해설

각 행은 차례로 삽입정렬, 선택정렬, 합병정렬, 퀵정렬의 중간 과정이다.

㉠은 앞의 8개만 정렬되어 있고 나머지는 입력 순서 그대로여서 정렬 구간을 하나씩 넓혀 가는 삽입정렬이다. ㉢은 정렬된 구간 3개(15~45의 7개, 9·18·23, 4·11·36)로 나뉘어 있어 부분 리스트를 정렬한 뒤 합치는 합병정렬이다.

㉡과 ㉣은 모두 최솟값을 앞으로 교환하는 선택정렬로 만들 수 있지만, ㉣은 맨 오른쪽 11을 피봇으로 분할한 결과(11 왼쪽에 4·9, 오른쪽에 더 큰 값)와도 같다. ㉡은 퀵정렬로 만들 수 없으므로 ㉡이 선택정렬, ㉣이 퀵정렬이다.

  • ㉡을 퀵정렬로 보는 나열: 18이 제자리에 오려면 그보다 먼저 남은 구간의 피봇 25가 제자리로 옮겨져야 하는데 ㉡에서는 25가 맨 끝에 남아 있다.
  • ㉠을 합병정렬로 보는 나열: 앞 8개만 정렬되고 나머지가 입력 그대로인 형태는 합병정렬의 분할·병합으로 나오지 않는다.
  • ㉢을 삽입정렬로 보는 나열: 뒤쪽 원소 9·18·23과 4·11·36이 입력과 다른 순서로 각각 정렬되어 있어 삽입정렬의 중간 결과가 아니다.

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

이어서 풀어보기

[7급 국가직 자료구조론] 17년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요7급 국가직 자료구조론 기출문제 암기장 전체 보기