다음 정렬 중에서 추가로 기억공간을 가장 많이 요구하는 정렬로 옳은 것… | [7급 국가직 자료구조론] 11년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 11년 1회차
다음 정렬 중에서 추가로 기억공간을 가장 많이 요구하는 정렬로 옳은 것은? (단, 각 정렬 방식은 일반적인 경우만 고려한다)
1
합병 정렬(merge sort)
2
선택 정렬(selection sort)
3
버블 정렬(bubble sort)
4
히프 정렬(heap sort)
해설
추가 기억공간을 가장 많이 요구하는 것은 합병 정렬이다.
합병 정렬은 두 부분 배열을 합칠 때 결과를 담을 임시 배열이 필요해 입력 크기에 비례하는 의 추가 공간을 쓴다.
- 선택 정렬은 제자리에서 교환만 하므로 상수 크기의 추가 공간이면 된다.
- 버블 정렬도 인접 원소 교환만 하는 제자리 정렬이다.
- 히프 정렬은 배열 자체를 히프로 만들어 정렬하므로 상수 크기의 추가 공간이면 된다.
오류나 개정된 내용이 보이면 알려주세요