[PYTHON] 파이썬_정렬 알고리즘 (병합정렬)

 

안녕하세요

겉바속촉입니다

!^^!

 

 

!!파이썬 시작하기!!

 

 

 

지난 번에는 

선택 정렬과 삽입 정렬에 대해 배웠습니다

 

2021/01/07 - [IT 일기 (상반기)/PYTHON] - [PYTHON] 파이썬_정렬 (선택정렬, 삽입정렬)

[PYTHON] 파이썬_정렬 (선택정렬, 삽입정렬)

 

 

이번에는 더 효율적인 정렬 방법

병합 정렬에 대해서

배워보도록 하겠습니다

 

 

 

 

 

---

 

 

 

더 효율적인 정렬 알고리즘

 

 

병합 정렬 : 더 빠른 정렬 알고리즘

 

1. 하나의 리스트를 두개의 균등한 크기로 분할
2. 분할된 부분 리스트를 정렬
3. 두 개의 정렬된 부분 리스트 합하기
4. 전체가 정렬된 리스트로 되는 것

 

다음 코드 참고

 

# 2개의 리스트를 하나의 정렬된 리스트로 반환
def merge(L1: list, L2: list) -> list:

    newL = [] 
    i1 = 0
    i2 = 0

    # [ 1, 1, 2, 3, 4, 5, 6, 7  ]
    # [ 1, 3, 4, 6 ]   [ 1, 2, 5, 7 ]
    #              i1            
    #                             i2 
    while i1 != len(L1) and i2 != len(L2):
        if L1[i1] <= L2[i2]:
            newL.append(L1[i1])
            i1 += 1
        else:
            newL.append(L2[i2])
            i2 += 1

    newL.extend(L1[i1:])               #남아있는 값들 새 리스트에 넣어주기(현재 예시는 남은 거 없음)
    newL.extend(L2[i2:])               #남아있는 값들 새 리스트에 넣어주기(현재 예시는 남은 7 추가됨)

    return newL                        #새롭게 만들어진 리스트 반환




def merge_sort(L: list) -> None:        # [ 1, 3, 4, 6, 1, 2, 5, 7 ] 라는 리스트 존재
    workspace = []                      # workspace란 리스트 만들어두기
    for i in range(len(L)):             # 0부터 7 인덱스 만들어서 순환
        workspace.append([L[i]])        # [ [1], [3], [4], [6], [1], [2], [5], [7] ]

    i = 0
    while i < len(workspace) - 1:
        L1 = workspace[i]               # [ [1], [3], [4], [6], [1], [2], [5], [7], [1,3],[4,6],[1,2],[5,7], [1,3,4,6],[1,2,5,7],[1,1,2,3,4,5,6,7]  ]
        L2 = workspace[i + 1]
        newL = merge(L1, L2)               
        workspace.append(newL)
        i += 2

    if len(workspace) != 0:
        L[:] = workspace[-1][:]        #workspace 리스트 뒤에서 첫번째 리스트 전체를 L리스트에 넣기

 

 

이제 얘를 포함해서

 

지난 포스팅에서 만들었던 선택정렬, 삽입정렬 합쳐서 시간 계산해볼게요

 

2021/01/07 - [IT 일기 (상반기)/PYTHON] - [PYTHON] 파이썬_정렬 (선택정렬, 삽입정렬)

[PYTHON] 파이썬_정렬 (선택정렬, 삽입정렬)

 

다음 코드의 아랫부분이 시간 측정 하는 메소드

 

# 2개의 리스트를 하나의 정렬된 리스트로 반환
def merge(L1: list, L2: list) -> list:

    newL = [] 
    i1 = 0
    i2 = 0

    # [ 1, 1, 2, 3, 4, 5, 6, 7  ]
    # [ 1, 3, 4, 6 ]   [ 1, 2, 5, 7 ]
    #              i1            
    #                             i2 
    while i1 != len(L1) and i2 != len(L2):
        if L1[i1] <= L2[i2]:
            newL.append(L1[i1])
            i1 += 1
        else:
            newL.append(L2[i2])
            i2 += 1

    newL.extend(L1[i1:])
    newL.extend(L2[i2:])

    return newL


def merge_sort(L: list) -> None:        # [ 1, 3, 4, 6, 1, 2, 5, 7 ]
    workspace = []
    for i in range(len(L)):             
        workspace.append([L[i]])        # [ [1], [3], [4], [6], [1], [2], [5], [7] ]

    i = 0
    while i < len(workspace) - 1:
        L1 = workspace[i]               # [ [1], [3], [4], [6], [1], [2], [5], [7], [1,3],[4,6],[1,2],[5,7], [1,3,4,6],[1,2,5,7],[1,1,2,3,4,5,6,7]  ]
        L2 = workspace[i + 1]
        newL = merge(L1, L2)               
        workspace.append(newL)
        i += 2

    if len(workspace) != 0:
        L[:] = workspace[-1][:]


import time, random

def built_in(L: list) -> None:
    L.sort()

def print_times(L: list) -> None:
    print(len(L), end='\t')
    for func in (selection_sort, insertion_sort, merge_sort, built_in):
        if func in (selection_sort, insertion_sort, merge_sort) and len(L) > 10000:
            continue

        L_copy = L[:]
        t1 = time.perf_counter()
        func(L_copy)
        t2 = time.perf_counter()
        print("{0:7.1f}".format((t2 - t1) * 1000.0), end="\t")

    print()

for list_size in [ 10, 1000, 2000, 3000, 4000, 5000, 10000 ]: 
    L = list(range(list_size))
    random.shuffle(L)
    print_times(L)

 

 

결과

 

 

지금 요 결과는 선택 정렬, 삽입 정렬, 병합 정렬 에 대해서 모두 비교하는 결과!!!

 

 

 

 

 

 

***참고해야할 명령 정리*** 리스트 i 설정 1. append   ->  11을 리스트에 넣어주기 --> 그럼 마지막 항목에 추가 2. extend  ->  리스트 확장 -->  항목이 아니라 리스트를 넣어주기 3. insert  ->  리스트에 원하는 위치에 항목 추가 --> 예시보면 0번 위치에 11 추가 list(인덱스, 값)