[알고리즘]병합정렬/퀵정렬

병합정렬이란?

분할 정복 알고리즘의 하나.문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음,결과를 모아서 원래의 문제를 해결하는 전략.즉, 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합쳐서 전체가 정렬된 리스트로 되게 하는 방법.

def Dsort(lt,rt):
	if lt<rt:
		mid=(lt+rt)//2
        Dsort(lt,mid) # 왼쪽자식 노드
        Dsort(mid+1,rt) # 오른쪽 자식 노드
        #왼쪽자식과 오른쪽 자식이 정렬된 후 본연의 일
        p1=lt #배열의 가장왼쪽이 시작점
        p2=mid+1
        tmp=[]
        while p1<=mid and p2<=rt:
        	if arr[p1]<arr[p2]:
            	tmp.append(arr[p1])
                p1+=1
            else:
            	tmp.append(arr[p2])
                p2+=1
        #안들어가고 남은 원소 리스트에 넣기
        if p1<=mid:
        	tmp=tmp+arr[p1:mid+1]
        if p2<=rt:
        	tmp=tmp+arr[p2:rt+1]
        for i in range(len(tmp)):
        	arr[lt+i]=tmp[i]



if __name__=="__main__":
	arr=[23,11,45,36,15,67,33,21]
    print("Before sort : ",end=' ')
    Dsort(0,7)
    print()
    print("After sort : ",end=' ')
    print(arr)
	

1. Dsort는 절반으로 나누어 구역을 2개를 생성한다.
2. 왼쪽 자식먼저 호출
3. 정렬된 2개의 부분을 최종적으로 합친다.
4. 마지막 자식노드에서 하나의 값만 남은 2개의 노드, 예를 들어 Dsort(0,1)에서는 11과 23 2개의 크기를 비교하고 합친다.

퀵정렬이란?

다른 원소와의 비교만으로 정렬을 수행하는 비교정렬.
문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략.
기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법.

def Qsort(lt,rt):
	if lt<rt:
    	pos=lt
        pivot=arr[rt]
        for i in range(lt,rt):
        	if arr[i]<=pivot:
            	arr[i],arr[pos]=arr[pos],arr[i]#SWAP
                pos+=1
         arr[rt],arr[pos]=arr[pos],arr[rt]#SWAP
         return
         Qsort(lt,pos-1)
         Qsort(pos+1,rt)
                
    
if __name__=="__main__":
	arr=[45,21,23,36,15,67,11,60,20,33]
    print("Before sort : ",end=' ')
    print(arr)
    Qsort(0,9)
    print("After sort : ",end=' ')
   	print(arr)

1.퀵정렬은 전위순회방식, 병합정렬은 후위순회방식
2. 중심값(pivot)값을 기준으로 왼쪽자식들은 중심값보다 작은 값들 분할,오른쪽자식들은 중심값보다 큰 값을 분할