알고리즘 - 병합 정렬, 퀵 정렬(Merge sort, Quick sort)

병합 정렬과 퀵 정렬은 간단한 정렬 알고리즘인 선택 정렬, 삽. 입 정렬, 버블 정렬에 비해 수행시간이 빠르다

또한 각자 수행시간 면에서 유리한 상황이 상이해 이에 대한 이해가 필요하다

 

1) 병합 정렬

 

원리:

1. 리스트를 반으로 나눈다

2. 두 부분을 재귀적으로 정렬한다

3. 정렬된 두 부분을 하나로 병합한다

 

코드(파이썬):

def mergesort(a,first,last):
	if first < last:
    	mid = (first + last) / 2
        mergesort(a,first,mid)
        mergesort(a,mid+1,last)
        merge(a,first,mid,last)

def merge(a,first,mid,last):
	f = first
    l = last
    k = 0
    b = []
    
    while(f < mid and l < last):
    	if a[f] <= a[l]:
        	b[k] = a[f]
            f += 1
		else:
        	b[k] = a[l]
            l += 1
		k += 1
	if f < mid:
    	for p in range(f,mid):
        	b[k] = a[p]
            k += 1
	else:
    	for p in range(l,last):
        	b[k] = a[p]
            k += 1
    
    a = b

시간복잡도:

최악의 경우 - O(n logn)

평균적인 경우 - O(n logn)

최선의 경우 - O(n logn)

 

2) 퀵 정렬

 

원리:

1. 리스트에서 pivot을 선택한다

2. pivot 보다 작거나 같은 수는 pivot 왼쪽으로, 큰 수는 pivot 오른쪽으로 이동시킨다

3. 두 부분을 재귀적(1,2번의 방법)으로 정렬한다

 

코드(파이썬):

def quicksort(a,left,right):
	if left < right:
    	pivotpoint = partition(a,left,right)
        quicksort(a,left,pivotpoint-1)
        quicksort(a,pivotpoint+1,right)

def partition(a,left,right):
	i = left+1
        j = right
        pivot = a[left]

        while i <= j:
            while i <= right and a[i] < pivot:
                i += 1
            while j >= left + 1 and a[j] >= pivot:
                j -= 1

            if i <= j:
                a[i],a[j] = a[j],a[i]
                i += 1
                j -= 1

            a[left],a[j] = a[j],a[left]
            return j

시간복잡도:

최악의 경우 - O(n^2)

평균적인 경우 - O(n logn)

최선의 경우 - O(n logn)