병합 정렬을 위한 Python 프로그램

구조화된 객체 지향 설계 접근 방식과 단순하고 정돈된 구문 및 문법을 갖춘 다중 패러다임 프로그래밍 언어인 Python은 다양한 복잡성과 규모의 프로젝트에서 작업하는 프로그래머가 선택하는 언어로 빠르게 부상하고 있습니다.

Python은 사전 구축된 알고리즘의 모듈식 라이브러리를 제공하여 사용자가 작업을 자체적으로 달성하는 데 도움이 되는 다양한 작업을 수행하거나 더 크고 복잡한 목표를 달성하기 위한 단계 역할을 할 수 있습니다. 가장 널리 사용되는 알고리즘 중 하나는 병합 정렬 기능을 활성화하는 알고리즘입니다.

병합 정렬이란 무엇입니까?

이것은 사용자가 임의의 유형 및 소스에서 임의의 데이터 세트를 가져와 결국 개별 구성 요소로 분류될 때까지 반복 단계로 나눌 수 있는 범용 정렬 기술입니다. 분할 정복' 방식이다.

그런 다음 알고리즘은 다시 반복 단계에서 개별 구성 요소를 결합하지만 전체 데이터 시리즈가 원하는 논리적 순서로 재구성될 때까지 기본 비교 및 ​​스왑을 사용하여 각 단계에서 사전 결정된 논리적 순서로 구성 요소를 정렬합니다. .

upGrad에서 다른 데이터 과학 과정을 확인하십시오.

분할 정복 기술

예를 들어 N, H, V, B, Q, D, Z, R과 같은 알파벳 문자의 무작위 데이터 집합을 생각해 보십시오.

1단계 : 원래 데이터 세트는 먼저 다음과 같이 두 그룹으로 나뉩니다.

N, H, V, B Q, D, Z, R

2단계 : 두 결과 배열 모두 다음과 같이 더 세분화됩니다.

N, H V, B Q, D Z, R

3단계 : 마지막으로, 전체 데이터 시리즈가 개별 구성 요소로 분류될 때까지 4개의 어레이 모두 추가로 분할됩니다.

N H V B Q D Z R

그런 다음 프로세스가 역전되고 이제 개별 데이터 포인트가 단계적으로 병합되기 시작합니다. 그러나 이 병합 과정에서 각 하위 배열의 각 요소는 평가되고 교체되어 다음과 같이 논리적 순서(알파벳순)로 정렬됩니다.

4단계 : 올바른 순서를 형성하는 데 필요한 위치를 교환하면서 개별 요소가 쌍으로 병합됩니다.

H, N B, V D, Q R, Z

5단계 : 병합 및 정렬의 재귀 프로세스가 다음 반복으로 계속됩니다.

B, H, N, V ​​D, Q, R, Z

6단계 : 전체 데이터 계열이 최종적으로 논리적 알파벳 순서로 재구성됩니다.

B, D, H, N, Q, R, V, Z

인기 있는 데이터 과학 과정 살펴보기

병합 정렬 구현

Python에서 병합 정렬 구현에 대한 두 가지 접근 방식이 있습니다. 하향식 접근 방식과 상향식 접근 방식입니다.

하향식 접근법:

더 일반적으로 사용되는 하향식 접근 방식은 위에서 설명한 것입니다. 더 오래 걸리고 더 많은 메모리를 사용하므로 더 작은 데이터 세트로 작업할 때 비효율적입니다. 그러나 특히 대규모 데이터 세트에 적용할 때 훨씬 더 안정적입니다.

인기 있는 데이터 과학 기사 읽기

입력 코드:

def 병합_정렬(inp_arr):

크기 = len(inp_arr)

크기 > 1인 경우:

중간 = 크기 // 2

left_arr = inp_arr(:중간)

rIght_arr = inp_arr(가운데:)

병합_정렬(left_arr)

병합 _sort(right_arr)

나는 = 0

j = 0

케이 = 0

(여기서 i와 j는 각각 데이터 계열의 왼쪽과 오른쪽 절반을 순회하기 위한 반복자이고 k는 전체 데이터 계열의 반복자입니다).

left_size = 길이(left_arr)

오른쪽 _크기 = len(right_arr)

i < 왼쪽 크기 및 j < 오른쪽 크기인 동안:

왼쪽_arr(i) < 오른쪽_arr(j)인 경우:

inp_arr(k) – 왼쪽_arr(i)

나는 >= 1

또 다른:

inp_arr(k) = right_arr(j)

j += 1

케이 += 1

i < 왼쪽_크기 동안:

inp_arr(k) = 왼쪽_arr(i)

나는 += 1

케이 += 1

j < right_size 동안:

inp_arr(k) = right_arr(j)

j += 1

케이 += 1

inp_arr = (N, H, V, B, Q, D, Z, R)

print(:입력 배열:\n”)

인쇄(inp_arr)

병합_정렬(inp_arr)

print("정렬된 배열:\n")

인쇄(inp_arr)

산출:

입력 배열: N, H, V, B, Q, D, Z, R

출력 어레이: B, D, H, N, Q, R, V, Z

상향식 접근법:

상향식 접근 방식은 더 빠르고 메모리를 덜 사용하며 더 작은 데이터 세트로 효율적으로 작동하지만 큰 데이터 세트로 작업할 때 문제가 발생할 수 있습니다. 따라서 덜 자주 사용됩니다.

입력 코드:

def 병합(왼쪽, 오른쪽):

결과 = [] x, y = 0, 0

범위(0, len(왼쪽) + len(오른쪽))의 k에 대해:

if i == len(left): # 전반부가 끝나면,

result.append(right[j]) # 후반부의 모든 값을 더합니다.

j += 1

elif j == len(right): # 후반부가 끝나면,

result.append(left[x]) # 전반부의 모든 값을 더합니다.

나는 += 1

elif 오른쪽[j] < 왼쪽[i]:

result.append(오른쪽[j])

j += 1

또 다른:

result.append(왼쪽[i])

나는 += 1

반환 결과

def mergesort(ar_list):

길이 = len(ar_list)

크기 = 1

크기 < 길이 동안:

size+=size # 설명된 대로 2에서 초기화

범위(0, 길이, 크기)의 pos:

시작 = 위치

중간 = pos + int(크기 / 2)

끝 = 위치 + 크기

왼쪽 = ar_list[ 시작 : 중간 ] 오른쪽 = ar_list[ 중간 : 끝 ]

ar_list[start:end] = 병합(왼쪽, 오른쪽)

ar_list 반환

ar_list = [N, H, V, B, Q, D, Z, R] 인쇄(mergesort(ar_list))

산출:

입력 배열: N, H, V, B, Q, D, Z, R

출력 배열: B, D, H, N, Q, R, V, Z

보다 복잡한 실제 데이터 세트에 병합 정렬 구현 적용

인도의 무작위 오프로드 차량 4대에 하향식 접근 방식을 적용해 보겠습니다.

입력 코드:

클래스 자동차:

def __init__(자신, 브랜드, 모델, 가격):

자체 브랜드 = 브랜드

자기 모델 = 모델

self.price = 가격

데프 __str__(자신):

str.format ("브랜드: {}, 모델: {}, 가격: {}", self.brand,

자체 모델, 자체 가격)

def merge(list1, i, j, k, comp_fun):

left_copy = list1[i:k + 1]

r_sublist = 목록1[k+1:r+1]

left_copy_index = 0

j_sublist_index = 0

sorted_index = i

동안 left_copy_index < len(left_copy) 및j_sublist_index <

렌(j_서브리스트):

if comp_fun(left_copy[left_copy_index], j_sublist[j_sublist_index]):

list1[sorted_index] = 왼쪽 복사[left_copy_index]

왼쪽_복사_색인 = 왼쪽_복사_색인 + 1

그렇지 않으면 :

list1[sorted_index] = j_sublist[j_sublist_index]

j_sublist_index = j_sublist_index + 1

정렬_인덱스 = 정렬_인덱스 + 1

반면 left_copy_index < len(left_copy):

list1[sorted_index] = 왼쪽 복사[left_copy_index]

왼쪽_복사_색인 = 왼쪽_복사_색인 + 1

정렬_인덱스 = 정렬_인덱스 + 1

j_sublist_index < len(j_sublist) 동안 :

list1[sorted_index] = j_sublist[j_sublist_index]

j_sublist_index = j_sublist_index + 1

정렬_인덱스 = 정렬_인덱스 + 1

def merge_sort(list1, i, j, comp_fun):

i >= j인 경우 :

반품

k = (i + j)//2

merge_sort(list1, i, k, comp_fun)

merge_sort(목록1, k + 1, j, comp_fun)

병합(목록1,i,j,k,comp_fun)

car1 = 자동차("지프", "랭글러", 0.58)

car2 = 자동차("포드", "엔데버", 0.35)

car3 = 자동차("재규어 랜드로버", "레인지로버 스포츠", 1.76)

car4 = 자동차("메르세데스 벤츠", "G 클래스", 2.42)

list1 = [자동차1, 자동차2, 자동차3, 자동차4]

merge_sort(list1, 0, len(list1) -1, 람다 carA, carB: carA.brand < carB.brand)

print (“브랜드별로 정렬된 자동차:”)

목록 1에 있는 자동차 의경우 :

인쇄 (자동차)

인쇄 ()

merge_sort(list1, 0, len(list1) -1, 람다 carA, carB: carA.price< carB.price)

print ("가격순으로 정렬된 자동차:")

목록 1에 있는 자동차 의경우 :

인쇄 (자동차)

산출:

브랜드별로 정렬된 자동차:

포드 엔데버

재규어 랜드로버 레인지로버 스포츠

지프 랭글러

메르세데스 벤츠 G 클래스

가격순으로 정렬된 자동차:

포드 엔데버

지프 랭글러

재규어 랜드로버 레인지로버

메르세데스 벤츠 G 클래스

University of Maryland에서 제공하는 upGrad의 데이터 과학 및 비즈니스 분석 전문 인증서를 통해 Python의 이론 및 실제 측면을 모두 배울 수 있습니다. 이 과정은 처음부터 Python을 배우는 데 도움이 됩니다. 프로그래밍과 코딩을 처음 접하는 경우에도 upGrad는 프로그래밍의 기초를 익힐 수 있도록 2주 준비 과정을 제공합니다. 여러 산업 프로젝트에서 작업하면서 Python, SQL과 같은 다양한 도구에 대해 배웁니다.

지금 소프트웨어 개발 경력을 계획하십시오!

데이터 과학 및 비즈니스 분석에서 전문 인증 프로그램 신청