다음 정렬 중에서 추가로 기억공간을 가장 많이 요구하는 정렬로 옳은 것… | [7급 국가직 자료구조론] 11년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 11년 1회차
다음 정렬 중에서 추가로 기억공간을 가장 많이 요구하는 정렬로 옳은 것은? (단, 각 정렬 방식은 일반적인 경우만 고려한다)
1
합병 정렬(merge sort)
2
선택 정렬(selection sort)
3
버블 정렬(bubble sort)
4
히프 정렬(heap sort)
해설

추가 기억공간을 가장 많이 요구하는 것은 합병 정렬이다.

합병 정렬은 두 부분 배열을 합칠 때 결과를 담을 임시 배열이 필요해 입력 크기에 비례하는 O(n)O(n)의 추가 공간을 쓴다.

  • 선택 정렬은 제자리에서 교환만 하므로 상수 크기의 추가 공간이면 된다.
  • 버블 정렬도 인접 원소 교환만 하는 제자리 정렬이다.
  • 히프 정렬은 배열 자체를 히프로 만들어 정렬하므로 상수 크기의 추가 공간이면 된다.

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

이어서 풀어보기

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