2022년 1회 정보처리기사 기출문제 36번

36. 분할 정복(Divide and Conquer)에 기반한 알고리즘으로 피벗(pivot)을 사용하며 최악의 경우 n(n-1)/2 회의 비교를 수행해야 하는 정렬(Sort)은?
① Selection Sort   ② Bubble Sort

③ Insert Sort         ❹ Quick Sort

 

---

해설:

이 문제에서 중요한 점은 분할 정복(Divide and Conquer) 방식, 피벗(pivot) 사용, 그리고 최악의 경우 n(n-1)/2 회의 비교를 수행하는 정렬 알고리즘을 찾는 것입니다.

각 정렬 알고리즘의 특성을 분석해보겠습니다.

1. Selection Sort

• Selection Sort는 분할 정복 방식이나 피벗을 사용하지 않습니다. 이 알고리즘은 매번 배열에서 최소값을 찾아 앞쪽으로 이동시키는 방식입니다. 최악의 경우에도 시간 복잡도는 **O(n²)**이지만, n(n-1)/2 비교를 수행하는 방식은 아닙니다.
• 따라서, Selection Sort는 정답이 아닙니다.

2. Bubble Sort

• Bubble Sort는 인접한 원소들을 비교하고 교환하는 방식입니다. 이 역시 분할 정복 방식이나 피벗을 사용하지 않습니다. 최악의 경우에 n(n-1)/2 회의 비교를 하게 되지만, 이 알고리즘은 피벗을 사용하지 않습니다.
• 따라서, Bubble Sort는 정답이 아닙니다.

3. Insert Sort

• Insert Sort는 배열에서 현재 원소를 적절한 위치에 삽입하는 방식입니다. 이 알고리즘은 분할 정복 방식을 사용하지 않으며, 피벗을 사용하지도 않습니다. 최악의 경우 시간 복잡도는 **O(n²)**로, n(n-1)/2 회의 비교를 하기는 하지만, 피벗을 사용하는 알고리즘은 아닙니다.
• 따라서, Insert Sort는 정답이 아닙니다.

4. Quick Sort

• Quick Sort는 분할 정복(Divide and Conquer) 방식으로 작동하는 알고리즘입니다. 이 알고리즘은 **피벗(pivot)**을 사용하여 배열을 나누고 정렬하는 방식입니다.
  • 최악의 경우에는 배열이 이미 정렬되어 있거나 거의 정렬된 상태일 때 피벗이 항상 배열의 첫 번째나 마지막 원소로 선택되어 배열을 균등하게 나누지 못하는 경우가 발생합니다. 이 경우 **O(n²)**의 시간 복잡도를 가지며, 최악의 경우에는 n(n-1)/2 회의 비교가 필요합니다.
  • Quick Sort는 분할 정복 방식으로 피벗을 사용하고, 최악의 경우 n(n-1)/2 회의 비교를 수행하는 정렬 알고리즘입니다.

---

결론:

정답은 ❹ Quick Sort입니다.
Quick Sort는 분할 정복(Divide and Conquer) 방식으로, **피벗(pivot)**을 사용하고 최악의 경우 n(n-1)/2 회의 비교를 수행하는 정렬 알고리즘입니다.