[java] 파이썬에서 병합 정렬 구현하기

15 Dec 2023

java

병합 정렬(Merge Sort)은 리스트를 분할하여 정렬한 다음, 합병하여 정렬하는 알고리즘입니다. 이 알고리즘은 안정적이며 대규모 데이터셋에 효과적으로 작동합니다. 파이썬에서 이 알고리즘을 구현하는 간단한 코드를 살펴보겠습니다.

병합 정렬 알고리즘

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        left_half = arr[:mid]
        right_half = arr[mid:]

        merge_sort(left_half)
        merge_sort(right_half)

        i = j = k = 0

        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1

        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1

        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1

사용 예시

arr = [5, 2, 7, 3, 9, 8, 4, 1, 6]
merge_sort(arr)
print("정렬된 배열:", arr)

위 코드를 실행하면, arr 리스트가 병합 정렬 알고리즘에 의해 정렬된 결과가 출력됩니다.

병합 정렬 알고리즘은 배열을 분할하여 정렬하고 병합하는 방식으로 동작하기 때문에 중복된 값이 있는 경우에도 안정적으로 정렬됩니다. 또한, 입력 크기에 상관없이 일정한 성능을 보장하여 대규모 데이터셋에도 효과적입니다.

이렇게 파이썬에서 병합 정렬을 구현할 수 있습니다.

참고 자료

파이썬 자습서: https://docs.python.org/3/tutorial/index.html
GeeksforGeeks: https://www.geeksforgeeks.org/merge-sort/