10병합 정렬

     

    ◼︎ 10-1 내림차순 병합 정렬

    오름차순 정렬에서 값을 비교하는 부분(g1[i1] < g2[i2])의 부등호 방향을 반대로 하면 내림차순 정렬 프로그램이 됩니다.

     

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

    # 내림차순 병합 정렬

    # 입력: 리스트 a

    # 출력: 없음(입력으로 주어진 a가 정렬됨)

     

    def merge_sort(a):

        n = len(a)

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

        if n <= 1:

            return

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

        mid = n // 2

        g1 = a[:mid]

        g2 = a[mid:]

        merge_sort(g1)

        merge_sort(g2)

        # 두 그룹을 합치는 과정(병합)

        i1 = 0

        i2 = 0

        ia = 0

        while i1 < len(g1) and i2 < len(g2):

            if g1[i1] > g2[i2]: # 부등호 방향 뒤집기

                a[ia] = g1[i1]

                i1 += 1

                ia += 1

            else:

                a[ia] = g2[i2]

                i2 += 1

                ia += 1

        while i1 < len(g1):

            a[ia] = g1[i1]

            i1 += 1

            ia += 1

        while i2 < len(g2):

            a[ia] = g2[i2]

            i2 += 1

            ia += 1

     

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

    merge_sort(d)

    print(d)

     

    ◉ 실행 결과

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

     

     

     

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