Merge Sort 과 Quick Sort 개념 및 활용 정리

728x90

미루고 미루던 Merge Sort와 Quick Sort 개념을 정리하고 공부해보겠습니다.

 

1. Quick Sort 

평균 Time complexity : O(nlogn)

최악의Time complexity : O(n^2)

 

특정 요소를 기준으로 크고 작은 그룹을 단계적으로 재배치/분할하여 정렬하는 알고리즘 

(요소 pivot 선택기준은 가장 왼쪽/오른쪽/랜덤/중간 등 다양한 값으로 선택가능)

 

Source: https://deepai.org/machine-learning-glossary-and-terms/quicksort-algorithm

 

---

 

2. Merge Sort

평균 Time complexity : O(nlogn)

최악의Time complexity : O(nlogn)

 

비교 기반의 정렬 알고리즘 동일한 길이의 조각으로 조각이 한개가 될 때까지 나누고

다시 쪼개진 조각들을 짝지어 작은 숫자, 큰 숫자 순으로 정렬해가면서 결국 하나의 정렬로 합치는 알고리즘

 

Source: https://www.researchgate.net/figure/Example-Illustrating-Merge-Sort-Operation-For-instance-with-a-list-containing-elements_fig1_341900290

 

 

3. Quick Sort / Merge Sort 차이점

두 가지 방법 모두 Divide and Conquer(분할정복) 알고리즘이라는 공통점이 있지만

Merge Sort 는 부분그룹을 동일한 길이를 기반으로 선정하고 , 그룹을 마지막 단계에 합치면서 정렬을 수행하지만

Quick Sort 는 그룹의 사이즈보다 비교 요소 대비 크고 작음을 기준으로 분할하고 그룹을 쪼개면서 정렬을 수행한다는 차이점이 있습니다.

 

따라서, Mergesort는 순차적인 접근에 용이한 linked list에 효율적으로 사용될 수 있고, Quicksort는 가끔 코딩 문제에 제약조건으로 추가적으로 메모리를 사용하지 않아야 한다는 제약조건이 있을 때 in-place 정렬을 위해서 사용되기에 좋습니다

 

---

 

 

4. Quick Sort / Merge Sort 파이썬 코드

(Geeks for Geeks 의 코드를 활용했습니다)

 

1) Quick Sort

def partition(array, low, high):
	pivot = array[high]        #가장 오른쪽값을 집어줍니다
	i = low - 1               

	for j in range(low, high):
		if array[j] <= pivot:
			i = i + 1
			(array[i], array[j]) = (array[j], array[i])
	(array[i + 1], array[high]) = (array[high], array[i + 1])
	return i + 1


def quickSort(array, low, high):
	if low < high:
		pi = partition(array, low, high)
		quickSort(array, low, pi - 1)
		quickSort(array, pi + 1, high)

 

2) Merge Sort

def mergeSort(arr):
	if len(arr) > 1:
    	 	mid = len(arr)//2
    	 	mergeSort(arr[:mid])
         	mergeSort(arr[mid:])
        
        	i = j = k =0
        
        	while i < len(arr[:mid]) and j <len(arr[mid:]):
            	if arr[:mid][i] < arr[mid:][j]:
            		arr[k] = arr[:mid][i]
                	i += 1
            	else:
            		arr[k] = arr[mid:][j]
                	j += 1
            	k += 1
        
        	#좌우 비교 리스트의 길이가 다를 경우, 남은 값을 통해 정렬
        	while i < len(arr[:mid]):
            	arr[k] = arr[:mid][i]
            	i += 1
            	k += 1
        	while j < len(arr[mid:]):
            	arr[k] = arr[mid:][j]
            	j += 1
            	k += 1

 

 

Source:

https://www.programiz.com/dsa/merge-sort

https://www.geeksforgeeks.org/python-program-for-quicksort/

https://www.interviewkickstart.com/learn/quicksort-vs-merge-sort

https://www.geeksforgeeks.org/quick-sort-vs-merge-sort/