Python 병합 정렬

이 포스팅에서는 Python 병합 정렬 알고리즘에 대해 알아봅니다.

병합 정렬은 분할 정복 기술을 기반으로 합니다.

우리가 해야 할 일은 배열을 2개의 부분 또는 하위 배열로 나누는 것뿐입니다. 그러면 해당 하위 배열은 다른 두 개의 동일한 부분으로 나뉩니다. 단일 요소가 이미 정렬되어 있으므로 각 부분에서 단일 요소를 얻을 때까지 이러한 방식으로 배열을 나눌 것입니다.

배열을 단일 요소를 갖는 다양한 하위 배열로 나눈 후 이제 정렬된 방식으로 이들을 정복하거나 병합할 차례입니다.

Python 병합 정렬

예
예를 살펴보겠습니다:

배열 [ 99, 21, 19, 22, 28, 11, 14, 18 ]이 있습니다.

Python 병합 정렬

배열에는 8개의 요소가 있습니다. 그것을 두 개의 동일한 부분으로 나눕니다.

Python 병합 정렬

 

그리고 각 부분이나 하위 배열에서 단일 요소를 얻을 때까지 분리를 반복합니다.

Python 병합 정렬

Python 병합 정렬

각 하위 배열에는 단일 요소가 있습니다. 이제 분할한 것과 동일한 방식으로 정렬된 방식으로 병합해야 합니다.

99와 21, 19와 22, 28과 11, 14와 18을 비교하고 더 작은 숫자를 먼저 배치합니다(오름차순).

Python 병합 정렬

여기에 정렬된 배열이 있습니다. 완전한 정렬된 배열을 얻을 때까지 계속 정복하세요.

Python 병합 정렬

그리고 마지막으로 배열이 정렬되었습니다.

Python 병합 정렬

이것은 이론적 개념이었습니다. 이제 프로그래밍에서 이 개념을 구현하는 방법을 살펴보겠습니다.

먼저 재귀를 사용하여 주어진 배열을 하위 배열로 나누는 알고리즘을 살펴보겠습니다.

두 번째로 두 개의 하위 배열을 정렬된 순서로 단일 배열로 병합하는 알고리즘을 살펴보겠습니다.

연산
병합정렬(배열)

단계:1-  n = 길이(배열) 설정

(n<2)이면 반환

단계:2-  mid = n/2로 설정

크기(mid)를 갖는 배열 "왼쪽"을 초기화합니다.

크기(n-mid)를 갖는 배열을 "오른쪽"으로 초기화합니다.

단계:3 -  i = 0에서 mid – 1까지

왼쪽 [i] = 배열[i]

[종료 루프]

               i = mid ~ n-1의 경우

오른쪽[i] = 배열[i]

[종료 루프]

단계:4-  mergesort(왼쪽) 호출

병합 정렬 호출(오른쪽)

통화 병합(왼쪽, 오른쪽, 배열)

병합(왼쪽, 오른쪽, 배열)

단계:1 – i = 0, j =0, k = 0으로 설정

[i,j,k는 각각 왼쪽, 오른쪽 및 배열의 ​​인덱스를 나타냅니다. ]

단계:2 –   while (i<길이(왼쪽) 및 j<길이(오른쪽)

{

If (왼쪽[i] < 오른쪽[j])

그런 다음 Array[k] = left[i]로 설정합니다.

i를 1만큼 늘립니다.

[if 문의 끝]

또 다른

배열[k] = 오른쪽[j] 설정

j를 1만큼 증가시킵니다.

[else 문 끝]

k를 1만큼 증가시킵니다.

[while 루프의 끝]

단계:3- while(i < 길이(왼쪽))

{

배열[k] = 왼쪽[i] 설정

나는 = 나는 + 1

k = k + 1

}

동안(j < 길이(오른쪽))

{

배열[k] = 오른쪽[j]

j를 1만큼 증가시킵니다.

k를 1만큼 증가시킵니다.

}

Python의 병합 정렬 프로그램

#array to be sorted

Array = [99,21,19,22,28,11,14,18]

 

#function for merging two sub-arrays

def merge(left, right, Array):

  i = 0

  j = 0

  k = 0

 

  while (i<len(left) and j<len(right)):

    if(left[i]<right[j]):

      Array[k] = left[i]

      i = i+1

    else:

      Array[k] = right[j]

      j = j+1

 

    k = k+1

  

  while(i<len(left)):

    Array[k] = left[i]

    i = i+1

    k = k+1

  

  while(j<len(right)):

    Array[k] = right[j]

    j = j+1

    k = k+1

 

#function for dividing and calling merge function

def mergesort(Array):

  n = len(Array)

  if(n<2):

    return

 

  mid = n/2

  left = []

  right = []

  

  for i in range(mid):

    number = Array[i]

    left.append(number)  

  

  for i in range(mid,n):

    number = Array[i]

    right.append(number)

 

  mergesort(left)

  mergesort(right)

 

  merge(left,right,Array)

 

#calling mergesort

mergesort(Array)

for i in Array:

  print i,

산출

11 14 18 19 21 22 28 99