정렬에 대한 설명으로 옳지 않은 것은? | [7급 국가직 자료구조론] 10년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 10년 1회차
정렬에 대한 설명으로 옳지 않은 것은?
1
배열에 저장되어 있는 자료들을 정렬할 경우, 합병정렬은 힙정렬보다 메모리 공간을 더 필요로 한다.
2
합병정렬로 n개의 자료를 정렬할 때, 정렬된 입력이나 그렇지 않은 입력이나 걸리는 시간은 항상 Θ(nlog⁡n)\Theta(n\log n)이다.
3
배열에 저장되어 있는 n개의 자료를 정렬하는 선택정렬에서, 최악의 경우 자료 비교횟수는 Θ(n2)\Theta(n^2)이고 최악의 경우 배열에서의 자료이동 횟수도 Θ(n2)\Theta(n^2)이다.
4
정렬된 입력에 대하여 퀵정렬(첫 번째 원소를 기준으로 분할)은 힙정렬보다 시간이 많이 걸린다.
해설

옳지 않은 것은 선택정렬의 최악 자료이동 횟수도 Θ(n2)\Theta(n^2)라는 설명이다.

선택정렬은 비교가 Θ(n2)\Theta(n^2)이지만 각 단계에서 최솟값과 한 번만 교환하므로 자료 이동은 최악에도 Θ(n)\Theta(n)이다.

  • 합병정렬과 힙정렬의 공간: 배열 합병정렬은 크기 n의 보조 배열이 필요하지만 힙정렬은 제자리 정렬이므로 옳다.
  • 합병정렬의 시간: 입력 상태와 관계없이 반씩 나누어 합병하므로 항상 Θ(nlog⁡n)\Theta(n\log n)으로 옳다.
  • 정렬된 입력의 퀵정렬: 첫 원소를 기준으로 하면 분할이 한쪽으로 치우쳐 Θ(n2)\Theta(n^2)이 되어 Θ(nlog⁡n)\Theta(n\log n)인 힙정렬보다 느리므로 옳다.

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

이어서 풀어보기

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