# 1. 정렬 알고리즘 **퀵 정렬**과 **병합 정렬**은 모두 분할 정복 (Divide and Conquer) 알고리즘이지만, 데이터를 나누는 방식과 메모리 사용 전략에서 큰 차이가 있다. ## 1) 퀵 정렬 (Quick Sort) ![b59fc05a-7803-4545-af45-394618a0bc2e](https://nfiqmgurjakbthpolcci.supabase.co/storage/v1/object/public/blog/content-images/rit-dive-60-day11/b59fc05a-7803-4545-af45-394618a0bc2e) - 퀵 정렬은 배열의 한 요소를 피벗 (pivot)으로 선택하고, 피벗보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 재배치함 - 이 과정에서 피벗은 정렬된 배열에서 항상 정확한 위치를 차지하게 됨 ###### 1. 배열의 마지막 요소 arr[4] = 40을 피벗으로 선택한다. 초기 포인터값은 i = -1, j = 0에서 시작한다. ![ad9d0b3a-93ef-4354-bfa6-ddcb68f964cb](https://nfiqmgurjakbthpolcci.supabase.co/storage/v1/object/public/blog/content-images/rit-dive-60-day11/ad9d0b3a-93ef-4354-bfa6-ddcb68f964cb) ###### 2. arr[j] < pivot -> 10 < 40이므로 i를 0으로 증가시키고 arr[i]와 arr[j]를 교환한다. ![adc8bc21-0705-48fa-902e-67f62e1ef8c7](https://nfiqmgurjakbthpolcci.supabase.co/storage/v1/object/public/blog/content-images/rit-dive-60-day11/adc8bc21-0705-48fa-902e-67f62e1ef8c7) ###### 3. arr[j] > pivot -> 80 > 40이므로 교환없이 다음 인덱스로 이동한다. ![fa6f9f96-c0e4-4ee3-9e51-718afe1b9910](https://nfiqmgurjakbthpolcci.supabase.co/storage/v1/object/public/blog/content-images/rit-dive-60-day11/fa6f9f96-c0e4-4ee3-9e51-718afe1b9910) ###### 4. arr[j] < pivot -> 30 < 40이므로, i를 1 증가시키고 arr[i]와 arr[j]를 교환한다. ![baf48238-9eda-45a5-98cc-9605f34df691](https://nfiqmgurjakbthpolcci.supabase.co/storage/v1/object/public/blog/content-images/rit-dive-60-day11/baf48238-9eda-45a5-98cc-9605f34df691) ###### 5. arr[j] > pivot -> 90 > 40이므로 교환 없이 다음 인덱스로 이동한다. ![ca20daeb-0527-4fb2-83a5-20b3c5800aa2](https://nfiqmgurjakbthpolcci.supabase.co/storage/v1/object/public/blog/content-images/rit-dive-60-day11/ca20daeb-0527-4fb2-83a5-20b3c5800aa2) ###### 6. j의 순회가 끝나면, 피벗을 올바른 위치로 이동시킨다. arr[i+1] = arr[2]와 arr[4] = 40을 교환하여 피벗이 정렬된 배열 내의 정확한 위치에 배치된다. ![ec505d09-ad3d-4008-9cbc-4630917b099f](https://nfiqmgurjakbthpolcci.supabase.co/storage/v1/object/public/blog/content-images/rit-dive-60-day11/ec505d09-ad3d-4008-9cbc-4630917b099f) - **특징** - **In-place 정렬**: 별도의 추가 메모리 공간이 거의 필요 없음 - **빠른 평균 속도**: 일반적으로 O(n log n) - **피벗 선택이 중요**: 피벗이 불균형하게 선택되면 최악의 경우 O(n²) - **예제 (Python)** ```python # partition 함수 def partition(arr, low, high): # pivot (기준 원소) 선택 pivot = arr[high] # i: 현재까지 발견된 pivot의 올바른 위치보다 하나 앞 인덱스 i = low - 1 # arr[low..high]를 순회하면서 pivot보다 작은 원소를 왼쪽으로 이동 # 매 반복마다 arr[low..i] 구간에는 pivot보다 작은 원소만 존재하게 된다 for j in range(low, high): if arr[j] < pivot: i += 1 swap(arr, i, j) # pivot을 더 작은 원소들 뒤로 이동시켜 최종 위치로 둔다 # 그리고 그 위치를 반환한다 swap(arr, i + 1, high) return i + 1 # swap 함수 def swap(arr, i, j): arr[i], arr[j] = arr[j], arr[i] # quickSort 함수 def quickSort(arr, low, high): if low < high: # pi는 partition 함수가 반환한 pivot의 최종 인덱스 pi = partition(arr, low, high) # 피벗보다 작은 부분과 큰 부분을 각각 재귀적으로 정렬한다 quickSort(arr, low, pi - 1) quickSort(arr, pi + 1, high) if __name__ == "__main__": arr = [10, 7, 8, 9, 1, 5] n = len(arr) quickSort(arr, 0, n - 1) for val in arr: print(val, end=" ") ``` - 출력 ``` 1 5 7 8 9 10 ``` ## 2) 병합 정렬 (Merge Sort) ![8ca7d44a-c9cf-416b-94a8-24c16ae2184c](https://nfiqmgurjakbthpolcci.supabase.co/storage/v1/object/public/blog/content-images/rit-dive-60-day11/8ca7d44a-c9cf-416b-94a8-24c16ae2184c) - 배열을 절반으로 나누고, 각 부분을 재귀적으로 정렬한 후 병합하여 전체를 정렬함 - 항상 균형적으로 분할되기 때문에, 성능이 일정하고 예측 가능함 ###### 1. 배열을 반으로 나눈다. ![e0e84930-50f7-4cb0-84ac-74dc9f664f86](https://nfiqmgurjakbthpolcci.supabase.co/storage/v1/object/public/blog/content-images/rit-dive-60-day11/e0e84930-50f7-4cb0-84ac-74dc9f664f86) ###### 2. 분할된 하위 배열을 다시 두 부분으로 나눈다. ![29b1ea03-b286-49bf-9e0e-6acc61488d9a](https://nfiqmgurjakbthpolcci.supabase.co/storage/v1/object/public/blog/content-images/rit-dive-60-day11/29b1ea03-b286-49bf-9e0e-6acc61488d9a) ###### 3. 길이 1의 배열부터 차례로 병합하여 정렬을 진행한다. ![4d7af7d8-2855-4967-90a6-92c72467f6b0](https://nfiqmgurjakbthpolcci.supabase.co/storage/v1/object/public/blog/content-images/rit-dive-60-day11/4d7af7d8-2855-4967-90a6-92c72467f6b0) ###### 4. 정렬된 하위 배열들을 병합하여 최종 정렬된 배열을 완성한다. ![ddc0aa44-daf0-4e86-ae21-125ddd673786](https://nfiqmgurjakbthpolcci.supabase.co/storage/v1/object/public/blog/content-images/rit-dive-60-day11/ddc0aa44-daf0-4e86-ae21-125ddd673786) - **특징** - **Stable Sort**: 동일한 값의 상대적 순서가 유지됨 - **항상 O(n log n)**: 분할이 균형적으로 이루어짐 - **추가 공간 필요**: 병합 시 임시 배열이 필요함 - **예제 (Python)** ```python def merge(arr, left, mid, right): n1 = mid - left + 1 n2 = right - mid # 임시 배열 생성 L = [0] * n1 R = [0] * n2 # L[], R[]에 데이터 복사 for i in range(n1): L[i] = arr[left + i] for j in range(n2): R[j] = arr[mid + 1 + j] i = 0 j = 0 k = left # 임시 배열을 원본 배열로 병합 while i < n1 and j < n2: if L[i] <= R[j]: arr[k] = L[i] i += 1 else: arr[k] = R[j] j += 1 k += 1 # L[]에 남은 요소가 있으면 복사 while i < n1: arr[k] = L[i] i += 1 k += 1 # R[]에 남은 요소가 있으면 복사 while j < n2: arr[k] = R[j] j += 1 k += 1 def mergeSort(arr, left, right): if left < right: mid = (left + right) // 2 mergeSort(arr, left, mid) mergeSort(arr, mid + 1, right) merge(arr, left, mid, right) if __name__ == "__main__": arr = [38, 27, 43, 10] mergeSort(arr, 0, len(arr) - 1) for i in arr: print(i, end=" ") print() ``` - 출력 ``` 10 27 38 43 ``` ## 3) 퀵 정렬과 병합 정렬 비교 |**비교 항목**|**퀵 정렬**|**병합 정렬**| |---|---|---| |**정렬 방식**|분할 후 정렬 (Partition)|정렬 후 병합 (Merge)| |**시간 복잡도 (평균)**|O(n log n)|O(n log n)| |**시간 복잡도 (최악)**|O(n²)|O(n log n)| |**공간 복잡도**|O(log n) (재귀 스택)|O(n) (임시 배열)| |**정렬 안정성**|불안정 (Unstable)|안정적 (Stable)| |**In-place 여부**|가능|불가능| |**분할 방식**|피벗 기준, 불균형 가능|항상 절반으로 균등 분할| |**성능 특성**|작은 배열에 유리|큰 데이터셋에 안정적| |**적합한 데이터 구조**|배열 (Array)|연결 리스트 (Linked List)| |**메모리 지역성 (Locality)**|좋음|나쁨| ## 4) 정리 - 두 알고리즘 모두 분할 정복을 사용하지만, 퀵 정렬은 피벗 중심의 제자리 정렬이고, 병합 정렬은 안정적인 병합 기반 정렬임 - 퀵 정렬은 메모리를 적게 사용하지만, 피벗이 비효율적으로 선택되면 성능이 급격히 저하될 수 있음 - 병합 정렬은 일관된 성능과 안정성을 보장하지만, 추가 메모리를 요구함 # 2. 출처 - **퀵 정렬**: https://www.geeksforgeeks.org/dsa/quick-sort-algorithm/ - **병합 정렬**: https://www.geeksforgeeks.org/dsa/merge-sort/ - **퀵 정렬과 병합 정렬 비교 표**: https://www.geeksforgeeks.org/dsa/quick-sort-vs-merge-sort/