Python에서 병합 정렬을 구현하는 방법은 무엇입니까?

이 블로그는 분할 및 정복 접근 방식을 기반으로합니다. Merge Sort는 문제를 하위 문제로 분할 한 다음 병합하여 솔루션을 정복하는 '분할 및 정복'알고리즘입니다. Merge Sort in에 대한이 블로그 아래 주제를 자세히 안내합니다.

• 파이썬에서 병합 정렬이란 무엇입니까?
• Divide and Conquer 접근 방식
• Python에서 병합 정렬 구현
• 병합 정렬 구현을위한 순서도
• 장점 및 사용법

파이썬에서 병합 정렬이란 무엇입니까?

Merge Sort는 입력 배열이 두 개의 반으로 나뉘어 진 후 개별적으로 정렬되고 다시 병합되어 솔루션에 도달하는 분할 및 정복 알고리즘을 기반으로합니다. merge () 함수는 정렬 된 항목을 병합하는 데 사용됩니다. .

Divide and Conquer 접근 방식

• 배열은 절반으로 분할되고 각 절반 크기가 1 또는 0이 될 때까지 프로세스가 반복됩니다.
• 크기 1의 배열은 간단하게 정렬됩니다.
• 이제 두 개의 정렬 된 배열이 하나의 큰 배열로 결합됩니다. 그리고 이것은 모든 요소가 결합되고 배열이 정렬 될 때까지 계속됩니다.

다음은 그림을 지우는 병합 정렬의 시각화입니다.

입력 배열 = [3,1,4,1,5,9,2,6,5,4]

자바 애플리케이션을 닫는 방법

이제 구현으로 넘어 갑시다.

Python에서 병합 정렬 구현

def mergeSort (nlist) : print ( 'Splitting', nlist) if len (nlist)> 1 : mid = len (nlist) // 2 lefthalf = nlist [: mid] righthalf = nlist [mid :] mergeSort (lefthalf) mergeSort (오른쪽 절반) i = j = k = 0 while i
 산출: 
$ python main.py 
 (‘분할’, [3, 1, 4, 1, 5, 9, 2, 6, 5, 4]) 
 (‘분할’, [3, 1, 4, 1, 5]) 
 (‘분할’, [3, 1]) 
 (‘분할’, [3]) 
 (‘병합’, [3]) 
 (‘분할’, [1]) 
 (‘병합’, [1]) 
 (‘병합’, [1, 3]) 
 (‘분할’, [4, 1, 5]) 
 (‘분할’, [4]) 
 (‘병합’, [4]) 
 (‘분할’, [1, 5]) 
 (‘분할’, [1]) 
 (‘병합’, [1]) 
 (‘분할’, [5]) 
 (‘병합’, [5]) 
 (‘병합’, [1, 5]) 
 (‘병합’, [1, 4, 5]) 
 (‘병합’, [1, 1, 3, 4, 5]) 
 (‘분할’, [9, 2, 6, 5, 4]) 
 (‘분할’, [9, 2]) 
 (‘분할’, [9]) 
 (‘병합’, [9]) 
 (‘분할’, [2]) 
 (‘병합’, [2]) 
 (‘병합’, [2, 9]) 
 (‘분할’, [6, 5, 4]) 
 (‘분할’, [6]) 
 (‘병합’, [6]) 
 (‘분할’, [5, 4]) 
 (‘분할’, [5]) 
 (‘병합’, [5]) 
 (‘분할’, [4]) 
 (‘병합’, [4]) 
 (‘병합’, [4, 5]) 
 (‘병합’, [4, 5, 6]) 
 (‘병합’, [2, 4, 5, 6, 9]) 
 (‘병합’, [1, 1, 2, 3, 4, 4, 5, 5, 6, 9]) 
 [1, 1, 2, 3, 4, 4, 5, 5, 6, 9]
 
 
값으로 전달 참조 Java로 전달
 병합 정렬 구현을위한 순서도 
 병합 정렬의 장점 및 사용법 
대부분의 다른 알고리즘은 파일 및 연결 목록과 같은 순차적 데이터 구조에서 성능이 좋지 않습니다. 이러한 구조에서 임의의 요소에 액세스하는 데는 일정한 일정한 시간이 아니라 선형 시간이 걸립니다. 그리고 병합 정렬의 특성은 이러한 데이터 구조를 쉽고 빠르게 만듭니다.병합 정렬의 가장 좋은 기능 중 하나는 비교 횟수가 적다는 것입니다. 비교 횟수는 O (n * log (n))이지만 퀵 정렬에 비해 상수 인자가 좋기 때문에 비교 기능이 느릴 때 유용합니다.또한 병합 정렬의 분할 및 정복 접근 방식은 병렬 처리에 편리합니다.
 이것으로 'Python에서 병합 정렬을 구현하는 방법'에 대한이 블로그의 끝 부분에 도달했습니다. 내용이 Python에 대한 지식에 가치를 더하기를 바랍니다. 다양한 응용 프로그램과 함께 Python에 대한 심층적 인 지식을 얻으려면 라이브에 등록 할 수 있습니다.  연중 무휴 지원 및 평생 액세스.