[Python] 분할 정복 - 퀵 정렬(quick sort) & 합병 정렬(merge sort)

[1] 합병 정렬 merge sort

*서로 떨어져있는 원소를 교환하는 것이 아니므로, 안정적임

 

*merge : 정렬을 마친 두 배열을 비교하여 합침 O(n)

*전체 시간 복잡도 = O(n log n)

 

(1) sorted 함수 사용하기

-> 정렬을 마친 상태가 아니더라도 적용가능하지만, 빠르지 않음

c=list(sorted(a+b)) 

 

(2) heapq 모듈의 merge() 함수 사용하기

->속도가 빠름

c=list(heapq.merge(a,b))

 

[2] 퀵 정렬 quick sort

퀵 정렬은 가장 잘 알려진 빠른 정렬 알고리즘이다.

pivot을 이용하여 분할 정복 해나가는 알고리즘으로, pivot을 어떤 식으로 정할지가 성능에 크게 영향을 미친다.

평균 시간 복잡도는 O(NlogN) 이며,

만약 매번 1개의 원소와 나머지 원소로 나누어진다면 (불 균등하게 분할된다면)..최악은 O(n^2)이다.

* 원소가 적은 경우에는 그다지 빠른 알고리즘이 아니니, 원소가 적을땐 오히려 단순 삽입 정렬이 더 나은 선택일수도..

 

1 - 분할시에 재귀함수로 퀵 정렬을 구현해 보았고

2- 스택으로 구현해봄

 

<Case 1 : pivot을 가운데 값이라고 뒀을 경우> 

 

1. 재귀함수 이용

def qsort(List,left,right):
    
    pl=left
    pr=right
    pivot=(right+left)//2
    #분할하기
    while pl<=pr:
        while List[pl] < List[pivot]:
            pl+=1
        while List[pr] > List[pivot]:
            pr-=1
        if pl<=pr: #값이 같아도 change -->why?
            List[pl],List[pr]=List[pr],List[pl]
            pl+=1
            pr-=1
            
    if left< pr:
        qsort(List,left,pr)
    if right > pl:
        qsort(List,pl,right)
    

List=[1,8,7,4,5,2,6,3,9]
qsort(List,0,len(List)-1)

print(*List)

 2. Stack 이용

from collections import deque

def qsort(List):
    stack=deque()
    left=0
    right=len(List)-1
    stack.append((left,right))
    
    while stack:
        
        pl,pr=left,right=stack.pop()
        
        pivot=(pl+pr)//2
        
        while pl <= pr:
            while List[pl] < List[pivot]:
                pl+=1
            while List[pr] > List[pivot]:
                pr-=1
            if pl <=pr:
                List[pl],List[pr]=List[pr],List[pl]
                pl+=1
                pr-=1
                
        if left < pr :
            stack.append((left,pr))
        if right > pl :
            stack.append((pl,right))
        
        
List=[1,8,7,4,5,2,6,3,9]
qsort(List)

print(*List)

<Case 2 : 적절한 pivot을 선택하는 방법 중 하나.>

 

-> 분할된 그룹의 맨 앞, 가운데, 끝 값을 정렬한 후 맨 끝 값 -1 번째를 가운데 값으로 바꾸고, 최종적으로 설정된 가운데 값을 pivot으로 설정하면 좀 더 최적화된 방법으로 정렬을 할 수 있다고한다.

 + ) 재귀함수로 코드를 작성하면 코드가 간결해지지만.. 내부적으로 비효율적이고 조금만 계산이 복잡해지면 stack overflow 문제를 발생시키기 때문에 스택으로 구현하였다.

 

from collections import deque

def qsort(List):
    stack=deque()
    left=0
    right=len(List)-1
    stack.append((left,right))
    
    while stack:
        lp,rp=left,right=stack.pop()
        
        #적절한 pivot구하기
        start=lp
        mid=(rp+lp)//2
        end=rp
        
        if List[start] > List[mid]:
            List[start],List[mid]=List[mid],List[start]
        if List[start] >List[end]:
            List[start],List[end]=List[end],List[start]
        if List[mid] > List[end]:
            List[mid],List[end]=List[end],List[mid]
            
        List[end-1],List[mid]=List[mid],List[end-1]
        
        pivot=mid
        
        while lp<=rp:
            while List[lp] <List[pivot]:
                lp+=1
            while List[rp] > List[pivot]:
                rp-=1
            if lp <=rp:
                List[rp],List[lp]=List[lp],List[rp]
                rp-=1
                lp+=1
        if start < rp:
            stack.append((start,rp))
        if end > lp:
            stack.append((lp,end))  
            
List=[5,8,4,2,6,1,3,9,7,0,3,5]
qsort(List)
print(*List)

 

ps. 실질적으로 알고리즘 PS를 할땐 sorted 내장 함수를 사용한다.!

*대부분의 프로그래밍 언어에서 지원하는 표준 정렬 라이브러리는 최악의 경우에도 O(NlogN)을 보장하도록 설계되어 있다고한다.

 

++) 엄청 빠른 알고리즘으로 계수 정렬(counting sort) 이 있는데 복잡도가 O(N+K)이다. 하지만 이것은 비교해서 정렬하는 것이 아닌, 빈도수로 정렬하기 때문에 정수로 이루어져있을 때와, 배열의 크기를 알고있을 때만 사용가능하다.