2쉽게 설명한 병합 정렬 알고리즘

     

    병합 정렬로 줄 세우는 방법을 떠올려 보면서 프로그램을 만들어 봅니다.

     

    icon_cakewalk 프로그램 10-1

     

    쉽게 설명한 병합 정렬 알고리즘

     

    ◉ 예제 소스 p10-1-msort.py

    # 쉽게 설명한 병합 정렬

    # 입력: 리스트 a

    # 출력: 정렬된 새 리스트

     

    def merge_sort(a):

        n = len(a)

        # 종료 조건: 정렬할 리스트의 자료 개수가 한 개 이하이면 정렬할 필요 없음

        if n <= 1:

            return a

        # 그룹을 나누어 각각 병합 정렬을 호출하는 과정

        mid = n // 2              # 중간을 기준으로 두 그룹으로 나눔

        g1 = merge_sort(a[:mid])  # 재귀 호출로 첫 번째 그룹을 정렬

        g2 = merge_sort(a[mid:])  # 재귀 호출로 두 번째 그룹을 정렬

        # 두 그룹을 하나로 병합

        result = []               # 두 그룹을 합쳐 만들 최종 결과

        while g1 and g2:          # 두 그룹에 모두 자료가 남아 있는 동안 반복

            if g1[0] < g2[0]:     # 두 그룹의 맨 앞 자료 값을 비교

                # g1 값이 더 작으면 그 값을 빼내어 결과로 추가

                result.append(g1.pop(0))

            else:

                # g2 값이 더 작으면 그 값을 빼내어 결과로 추가

                result.append(g2.pop(0))

        # 아직 남아 있는 자료들을 결과에 추가

        # g1과 g2 중 이미 빈 것은 while을 바로 지나감

        while g1:

            result.append(g1.pop(0))

        while g2:

            result.append(g2.pop(0))

        return result

     

    d = [6, 8, 3, 9, 10, 1, 2, 4, 7, 5]

    print(merge_sort(d))

     

    신간 소식 구독하기
    뉴스레터에 가입하시고 이메일로 신간 소식을 받아 보세요.