스택 - 분할정복 알고리즘

1. 분할 정복 알고리즘

• 설계 전
  • 분할(Divide) : 해결할 문제를 여러 개의 작은 부분으로 나눕니다.
  • 정복(Conquer) : 나눈 작은 문제를 각각 해결합니다.
  • 통합(Combine) : (필요하다면) 해결된 해답을 모읍니다.

---

---

---

---

2. 퀵 정렬

• 주어진 배열을 두 개로 분할하고, 각각을 정렬합니다.
  • 합병정렬과 비슷
• 다른 점 1 : 합병정렬은 그냥 두 부분으로 나누는 반면에, 퀵정렬은 분할할 때, 기준 아이템(pivot item) 중심으로, 이보다 작은 것은 왼편, 큰 것 오른편에 위치시킵니다.
• 다른 점 2 : 각 부분 정렬이 끝난 후, 합병정렬은 "합병"이란 후처리 작업이 필요하나, 퀵정렬은 필요로 하지 않습니다. 

---

---

---

---

---

---

---

---

---

---

---

---

• 퀵정렬의 최악의 시간 복잡도는 O(n²)로, 합병정렬에 비해 좋지 못합니다.
• 그런데, 왜 "빠른" 정렬이라고 했을까요?
• 이는 퀵정렬의 평균 복잡도는 nlogn이기 때문입니다.

---

3. 정렬 알고리즘 비교