자료구조 09. 정렬 O(nlogn)-퀵소트, 머지소트

2019.07.04 TIL

(TIL은 스스로 이해한 것을 바탕으로 정리한 것으로 오류가 있을 수 있습니다)

# 질문에 답하기

1. 정렬 O(nlogn) - 자료의 구조가 많아 질수록 정렬의 효율이 높아진다.

2. 퀵소트

3. 머지소트

1. 퀵소트

1. 하나의 스택프레임 안에서 conquer를 한 이후에 다시 호출 할 때 divide가 되는 것이다.
2. 파티션을 알고 있으면 좋다.
   1. 피벗을 기준으로 왼쪽에는 작은 값이, 큰 값은 오른쪽에 오도록 몰아버리는 것
   2. conquer이다.
3. pivot은 인덱스가 아니라 값이다.(처음 혹은 끝, 중간)
4. 재귀 함수 사용

def quick_sort(arr, start, end):
    #기저조건(base case)
    if start >= end:
        return

    left = start
    right = end
    pivot = arr[(left+right)//2] #정수형 나누기 해야됨

    #파티션
    #left와 right가 교차하기 전이라면 파티션을 계속 수행한다.
    while left <= right:
        #left가 언제 멈춰야 하나?
        while arr[left]<pivot:
            left+=1
        #right가 언제 멈춰야 하나?
        while arr[right]>pivot:
            right-=1

        # left와 right가 교차하지 않았다면 교환
        if left <= right:
            arr[left], arr[right] = arr[right], arr[left]
            left+=1
            right-=1


    quick_sort(arr, start, right)
    quick_sort(arr, left, end)


if __name__ == "__main__":
    arr = [7, 2, 5, 12, 6, 10, 8, 1, 3]
    start = 0
    end = 7
    quick_sort(arr, start, len(arr)-1)
    print(arr)

2. 머지소트

• 먼저 다 나누고 정렬을 한다.
• 하나 하나가 다 스택프레임으로 쌓인다.
• 다 나눈 이후에 왼쪽은 left 오른쪽은 right

def merge(arr, start, mid, end):
    left = start
    right = mid + 1
    temp = []  #로컬 베리어블이라서 업데이트 안하면 사라져버린다.


    # 둘 중에 하나라도 범위를 벗어나기 전가지
    while left<= mid and right <= end:
        if arr[left] <= arr[right]:
            temp.append(arr[left])
            left += 1
        else:
            temp.append(arr[right])
            right += 1

    #만약에 남아있는 것이 right라면
    #right를 돌면서 temp에에 넣는다.

    while right <= end:
        temp.append(arr[right])
        right +=1

    while left <= mid:
        temp.append(arr[left])
        left += 1

    # arr에 temp를 업데이트 하는 코드
    arr[start:end+1] = temp
    print(temp)


def merge_sort(arr, start, end):
    #base_case
    if start >= end:
        return

    mid = (start+end)//2

    #divide
    merge_sort(arr, start, mid)
    merge_sort(arr, mid+1, end)

    #conquer
    merge(arr, start, mid, end)


if __name__ == "__main__":
    arr = [3,6,9,1,3,5,7,8]
    start = 0
    end = len(arr)-1
    merge_sort(arr, start, end)
    print(str(arr))