[합병정렬 알고리즘] 합병 정렬의 흐름

프로그래밍 대학에서 합병 정렬 알고리즘을 다루는 강의가 개최되었습니다. 강의를 듣기로 결정한 지수와 영희는 합병 정렬을 더 잘 이해하기 위해 실제로 정렬 과정을 파악하고 싶어합니다.

주어진 N개의 숫자들로 이루어진 리스트를 합병 정렬 알고리즘을 사용하여 오름차순으로 정렬하는 함수를 구현하세요.

입력
정수 리스트 numbers (1 이상 100 이하의 정수를 요소로 가진 리스트)

출력
합병 정렬 알고리즘에 의해 정렬된 리스트

예제

def merge_sort(numbers):
    # 합병 정렬 알고리즘을 사용하여 numbers를 정렬하고 결과를 반환하는 함수를 구현해주세요.
    pass

# 테스트
numbers = [10, 5, 8, 3, 2, 7]
sorted_numbers = merge_sort(numbers)
print(sorted_numbers)  # 예상 출력: [2, 3, 5, 7, 8, 10]

힌트
합병 정렬 알고리즘은 분할 정복 기법을 사용하여 리스트를 정렬하는 알고리즘입니다. 리스트를 두 개로 분할한 후, 각각을 재귀적으로 정렬한 후 합병하여 전체 리스트를 정렬합니다. 이러한 과정을 반복하여 전체 리스트가 정렬되도록 합니다.

 

정답

def merge_sort(numbers):
    # 합병 정렬 알고리즘을 사용하여 numbers를 정렬하는 함수를 구현해주세요.
    if len(numbers) <= 1:
        return numbers

    mid = len(numbers) // 2
    left = numbers[:mid]
    right = numbers[mid:]

    left = merge_sort(left)
    right = merge_sort(right)

    return merge(left, right)


def merge(left, right):
    merged = []
    left_index, right_index = 0, 0

    while left_index < len(left) and right_index < len(right):
        if left[left_index] < right[right_index]:
            merged.append(left[left_index])
            left_index += 1
        else:
            merged.append(right[right_index])
            right_index += 1

    while left_index < len(left):
        merged.append(left[left_index])
        left_index += 1

    while right_index < len(right):
        merged.append(right[right_index])
        right_index += 1

    return merged

# 테스트
numbers = [10, 5, 8, 3, 2, 7]
sorted_numbers = merge_sort(numbers)
print(sorted_numbers)  # 예상 출력: [2, 3, 5, 7, 8, 10]

코드 해설:

위 정답 코드는 합병 정렬 알고리즘을 구현한 코드입니다.

merge_sort 함수는 재귀적인 방법을 사용하여 리스트를 합병 정렬 알고리즘으로 정렬합니다. 함수는 다음과 같은 과정을 거쳐서 리스트를 정렬합니다.

입력 리스트의 길이가 1 이하인 경우, 입력 리스트를 그대로 반환하여 정렬이 끝납니다.
리스트를 두 개로 분할합니다. 왼쪽 리스트(left)와 오른쪽 리스트(right)로 분할합니다. 분할은 리스트의 중간을 기준으로 합니다.
왼쪽 리스트와 오른쪽 리스트를 각각 재귀적으로 정렬합니다.
정렬이 끝난 왼쪽 리스트와 오른쪽 리스트를 합병(merge)하여 정렬된 리스트를 반환합니다.
merge 함수는 두 개의 정렬된 리스트를 하나로 합병하는 함수입니다. 합병 과정에서 두 리스트의 원소를 비교하여 작은 원소부터 차례로 합병한 결과를 반환합니다.

따라서 위의 예제에서 주어진 numbers 리스트가 [10, 5, 8, 3, 2, 7]이었다면, 함수 merge_sort는 [2, 3, 5, 7, 8, 10]을 반환합니다. 이는 주어진 numbers를 오름차순으로 정렬한 결과입니다.