Python을 사용하여 병합 정렬을 구현하는 방법

병합 정렬은 고전적인 정렬 알고리즘의 핵심 아이디어는 정렬할 배열을 여러 하위 배열로 나누고, 이러한 하위 배열을 정렬한 다음, 마지막으로 정렬된 하위 배열을 순서 있는 배열로 병합하는 것입니다. 병합 정렬은 시간 복잡도가 O(nlogn)인 비교적 효율적인 정렬 알고리즘입니다.

이 글에서는 Python에서 병합 정렬을 구현하는 방법을 설명하겠습니다.

1. 병합 정렬 구현 아이디어

병합 정렬 구현 아이디어는 분할 정복과 병합이라는 두 부분으로 구성됩니다. 구체적인 구현 단계는 다음과 같습니다.

1) 정렬할 배열을 연속적으로 2개로 나누고, 왼쪽과 오른쪽 부분을 재귀적으로 정렬합니다.

2) 정렬된 왼쪽 부분과 오른쪽 부분을 순서 있는 배열로 병합합니다.

2. Python을 사용하여 분할 정복 구현

분할 정복은 병합 정렬의 핵심 아이디어로 분할 정복 부분을 먼저 구현해야 합니다.

코드는 다음과 같습니다.

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left_arr = merge_sort(arr[:mid])
    right_arr = merge_sort(arr[mid:])
    return merge(left_arr, right_arr)

이 함수에서는 먼저 배열 길이가 1보다 작거나 같은지 확인한 다음 배열을 직접 반환합니다. 그렇지 않으면 배열을 두 개로 나누고 각각 왼쪽과 오른쪽 부분을 재귀적으로 정렬한 다음 마지막으로 정렬된 왼쪽 부분과 오른쪽 부분을 병합해야 합니다.

2.1 합병 구현

분할과 정복을 바탕으로 병합 부분을 구현해야 합니다.

코드는 다음과 같습니다:

def merge(left_arr, right_arr):
    i, j = 0, 0
    result = []
    while i < len(left_arr) and j < len(right_arr):
        if left_arr[i] < right_arr[j]:
            result.append(left_arr[i])
            i += 1
        else:
            result.append(right_arr[j])
            j += 1
    result += left_arr[i:]
    result += right_arr[j:]
    return result

이 함수에서는 먼저 왼쪽과 오른쪽 부분에서 각각 비교할 요소를 가리키는 포인터 i와 j를 초기화합니다. 그런 다음 왼쪽과 오른쪽 요소를 지속적으로 비교하고 더 작은 요소를 결과 목록에 추가한 다음 포인터를 오른쪽으로 이동합니다. 마지막으로 남은 모든 요소를 ​​결과 목록에 추가하여 정렬된 배열로 끝납니다.

3. 전체 코드

분할 정복 및 병합 부분을 결합한 전체 코드는 다음과 같습니다.

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left_arr = merge_sort(arr[:mid])
    right_arr = merge_sort(arr[mid:])
    return merge(left_arr, right_arr)

def merge(left_arr, right_arr):
    i, j = 0, 0
    result = []
    while i < len(left_arr) and j < len(right_arr):
        if left_arr[i] < right_arr[j]:
            result.append(left_arr[i])
            i += 1
        else:
            result.append(right_arr[j])
            j += 1
    result += left_arr[i:]
    result += right_arr[j:]
    return result

4. Testing

병합 정렬 코드가 올바른지 확인하려면 테스트를 수행해야 합니다. .

코드는 다음과 같습니다.

arr = [5, 3, 8, 6, 4, 7, 2, 1]
print(merge_sort(arr))

출력 결과는 다음과 같습니다.

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

테스트 결과에 따르면 병합 정렬 코드가 올바른 것으로 나타났습니다.

위 내용은 Python을 사용하여 병합 정렬을 구현하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!