[TIL][TUE] 병합정렬/퀵정렬

관련 학습 포인트: 분할정복, 재귀

Divide and Conquer

학습포인트

• Divide and Conquer 알고리즘 : merge sort / quick sort
• persucode template?
• 분할과 정복 타입의 알고리즘의 시간복잡도를 측정하기 위한 master theorem

분할과 정복 들어가기

개념

같거나 연관된 타입의 2개 이상의 하위문제로 문제를 쪼개는(분할, divide) 기법. 어디까지 쪼개냐 하면, 바로 충분히 간단하게 직접 해결할 수 있을 때까지 쪼개어 계산(정복, conquer)하고, 최종결론을 형성하기위해 하위문제의 결과와 결합한다.

1. Divide: 문제 S를 하위문자의 집합으로 나눈다.
2. Conquer: 각각의 문제를 재귀적으로 푼다.
3. Combine/merged: 각각의 하위문제의 결과를 결합한다.

재귀와의 차이점:

재귀는 하나의 더 작은 하위문제로 쪼개지만, 분할정복은 2개 이상의 문제로 쪼갠다. 이 재귀는 Binary search 과 같이 **부분 정복 알고리즘(decrease and conquer) 이라고 불린다.

병합 정렬 Merge Sort

방향에 따라 Top-down / Bottom-up 접근 방식으로 나뉜다.

Top-down

하향식(top-down, 아래로 가는 방법) 접근: 자연적으로 재귀를 사용하는 방식으로 셜명가능하다.

#step 0 
[1, 5, 3, 2, 8, 7, 6, 4]
#step 1 DIVIDE & CONQUER
#2개의 리스트로 분할한다.
#재귀적으로 이전 단계를 반복한다
[1, 5, 3, 2] [8, 7, 6, 4]
[1, 5] [3, 2] [8, 7] [6, 4]
[1] [5] [3] [2] [8] [7] [6] [4]
#setp2 MERGE
[1, 5] [2, 3] [7, 8] [4, 6]
[1, 2, 3, 5] [4, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]

1. 첫번째 단계에서 하나의 배열을 두개의 하위배열로 분할한다. (divide)
2. 다음 단계에서 이전 단계의 하위 배열을 재귀적으로 정렬한다. (conquer)
   • 여기서의 재귀는 비어있거나/ 하나의 요소만을 갖는 base case에 도달한다! ([1,5,3,2]→[1] [5] [3] [2])
3. 마지막으로 위 단계에서 정렬된 하위 목록을 반복적으로 병합하여 정렬된 요소의 최종 리스트를 얻는다. (combine)

두개의 정렬된 배열을 결합하는 건 선형 시간 복잡도(O(n))를 가질 수 있으며, n은 두 리스트를 병합하는 총 길이이다.

def merge_sort(arr):
    n=len(arr)
    pivot=int(n//2)
    
    if n==1:#재귀 호출이 끝나는 시점(최종포인트)
        return arr
    #그때까지 arr을 나누어 자기자신을 호출하여 전달한다.
    left_list=merge_sort(arr[:pivot])
    right_list=merge_sort(arr[pivot:])
    #작업내용(정렬)은 merging 함수에서 시행.
    #merge까지 한다. 
    return merging(left_list, right_list)
    
def merging(left_list, right_list):
    left_cur=0
    right_cur=0
    res=[]
    #왼쪽/오른쪽로 나뉜 배열/하나의 원소에서 하나씩 골라 비교한다.
    #cur는 각 배열을 가리키는 커서(포인터)
    #각 배열의 끝까지 이동하며 
    while left_cur<len(left_list) and right_cur<len(right_list):
        if left_list[left_cur]<right_list[right_cur]:
            res.append(left_list[left_cur])
            left_cur+=1
        else:
            res.append(right_list[right_cur])
            right_cur+=1
    
    #왼/오 리스트의 나머지를 넣는다. 이미 정렬된 배열이므로 그대로 넣어주기만 한다.
    res.extend(left_list[left_cur:])
    res.extend(right_list[right_cur:])
    
    return res

arr=[1,5,3,2,8,7,6,4]
print(merge_sort(arr))

bottom-up

1. 리스트를 한 개의 요소만 가진 하위리스트로 나눈다. (↔2개의 하위 배열로 나눈다)
2. 나뉜 하위리스트들은 이미 정렬이 완료됐다.(한개뿐이니까)
3. 하나의 리스트만 남을 때까지 한번에 이 하위리스트들 2개를 병합해간다.

[1,5,3,2,8,7,6,4]
[1] [5] [3] [2] [8] [7] [6] [4]
[1,5] [2,3] [8,7] [4,6]
[1,2,3,5] [4,6,7,8]
[1,2,3,4,5,6,7,8]

[병합정렬] 시간복잡도

O(n log n)

1. O(1)씩 걸리는 분할작업이 원소가 하나 남을 때까지 N번(N=자료의 갯수) 반복되므로 총 시간복잡도는 O(N)이다.
2. 병합할 때 매 level마다 N개의 요소들이 있다. 각 level당 병합 과정을 완료하려면 O(N)의 시간이 걸리고, 총합 logN level이 존재하므로 병합 과정의 전체적인 복잡도는 O(N log N)이다.

[병합정렬] 공간복잡도

하위 리스트들을 병합 고정 중 매 라운드마다 병합 결과를 버퍼에 붙잡고 있어야 하기 때문에 O(N)이다. (N=input list의 길이)

퀵 정렬

편을 갈라 정렬한다.

1. pivot값을 선택하고 리스트를 두개의 하위 리스트로 나눈다. 하나의 하위리스트는 피봇 값보다 적은 값을, 다른 하나는 피봇보다 크거나 같은 값을 갖는다. 이 과정은 파티셔닝(partioning)이라고도 불리며, 피봇을 선택하는 전략은 다양할 수 있다. 목록의 첫번째 요소나 어떤 한 요소를 랜덤하게 뽑을 수 있다.
2. 두개의 하위 배열로 재귀적으로 정렬한다. 그러다보면 기준점이 되는 pivot이 여러 요소가 있는 배열 중 하나에서 원소 하나만을 선택하는 때가 오고 그 양옆으로 작거나 크거나 같은 경우들이 있게 된다. 각자 정렬이 완료되고 각각 쪼개진 두개의 배열은 왼쪽은 오른쪽보다 작은, 정렬된 원소들이 자리하고 오른쪽은 그 이상의 원소들이 정렬되어 존재하게 된다.

1 20 8 13 >4< 19 22 49 12
4를 기준으로 왼쪽은 작은 정렬
오른쪽은 큰 수가 있는지 체크한다
인덱스 0에서 4(index:5)까지 오면서 4보다 큰 수가 있는지 체크하고 
인덱스 -1에서 4(index:5)까지 오면서 4보다 작은 수가 있는지 체크한다 
발견시 서로 교환하고 left point와 right point의 수를 증/감한다. 

이 과정을 또다시 
1 20 8 13 4  ]  [ 19 22 49 12 
이 두 배열을 하나의 배열로 생각하고 반복한다. 

재귀가 사용된다.

10.17 러프하게 정리, 다듬기 필요.