2021년 2회 정보처리기사 기출문제 32번

32. 정렬된 N개의 데이터를 처리하는 데 O(Nlog2N)의 시간이 소요되는 정렬 알고리즘은?

❶ 합병정렬   ② 버블정렬

③ 선택정렬   ④ 삽입정렬

 

 

이 문제는 O(N log N) 시간 복잡도를 갖는 정렬 알고리즘을 묻고 있습니다.

각각의 정렬 알고리즘에 대해 시간 복잡도를 알아보겠습니다:

① 합병정렬 (Merge Sort)

• 시간 복잡도: 합병정렬은 분할 정복 방식의 알고리즘으로, 주어진 배열을 반으로 나누어 각각 정렬한 후 병합하는 방식입니다.
• 시간 복잡도는 **O(N log N)**입니다.
  • 설명: 배열을 반으로 나누는 데 O(log N)의 시간이 걸리고, 나눈 배열을 합치는데 O(N)의 시간이 걸리므로 총 시간 복잡도는 **O(N log N)**입니다.
• 결론: 합병정렬은 O(N log N)의 시간 복잡도를 가집니다.

② 버블정렬 (Bubble Sort)

• 시간 복잡도: 버블정렬은 인접한 두 원소를 비교하고 교환하는 방식으로 정렬합니다.
• 시간 복잡도는 **O(N²)**입니다.
  • 설명: 매번 비교하고 교환하는 작업이 최악의 경우 O(N)번씩 이루어지기 때문에 총 시간 복잡도는 **O(N²)**입니다.
• 결론: 버블정렬은 **O(N²)**의 시간 복잡도를 가집니다.

③ 선택정렬 (Selection Sort)

• 시간 복잡도: 선택정렬은 배열에서 가장 작은 값을 찾아 맨 앞의 값과 교환하는 방식입니다.
• 시간 복잡도는 **O(N²)**입니다.
  • 설명: 선택정렬은 전체 배열에서 최소값을 찾는데 O(N) 시간이 걸리고, 이를 반복하므로 총 시간 복잡도는 **O(N²)**입니다.
• 결론: 선택정렬은 **O(N²)**의 시간 복잡도를 가집니다.

④ 삽입정렬 (Insertion Sort)

• 시간 복잡도: 삽입정렬은 배열을 순차적으로 탐색하며 각 원소를 이미 정렬된 부분에 적절한 위치에 삽입하는 방식입니다.
• 시간 복잡도는 **O(N²)**입니다.
  • 설명: 최악의 경우 각 원소를 삽입할 때 O(N) 시간이 걸리며, 이를 N번 반복하므로 총 시간 복잡도는 **O(N²)**입니다.
• 결론: 삽입정렬은 **O(N²)**의 시간 복잡도를 가집니다.

결론

O(N log N) 시간 복잡도를 가지는 정렬 알고리즘은 **합병정렬 (Merge Sort)**입니다.

따라서 정답은 ① 합병정렬입니다.