데이터 구조-병합 정렬 알고리즘
병합 정렬은 나누기 및 정복 기술을 기반으로하는 정렬 기술입니다. 최악의 경우 시간 복잡도가 Ο (n log n) 인 경우 가장 존경받는 알고리즘 중 하나입니다.
병합 정렬은 먼저 배열을 동일한 절반으로 나눈 다음 정렬 된 방식으로 결합합니다.
병합 정렬은 어떻게 작동합니까?
병합 정렬을 이해하기 위해 정렬되지 않은 배열을 다음과 같이 사용합니다.
병합 정렬은 원자 값이 달성되지 않는 한 전체 배열을 반복적으로 동일한 반으로 나누는 것을 알고 있습니다. 여기에서 8 개 항목의 배열이 크기 4의 두 배열로 나뉩니다.
원본에있는 항목의 모양 순서는 변경되지 않습니다. 이제이 두 배열을 반으로 나눕니다.
우리는이 배열을 더 나누고 더 이상 나눌 수없는 원자 가치를 얻습니다.
이제 우리는 그것들을 분해 한 것과 똑같은 방식으로 결합합니다. 이 목록에 제공된 색상 코드를 참고하십시오.
먼저 각 목록의 요소를 비교 한 다음 정렬 된 방식으로 다른 목록으로 결합합니다. 14와 33이 정렬 된 위치에 있음을 알 수 있습니다. 27과 10을 비교하고 2 개 값의 대상 목록에서 10을 먼저 입력 한 다음 27을 입력합니다. 19와 35의 순서를 변경하는 반면 42와 44는 순차적으로 배치됩니다.
결합 단계의 다음 반복에서는 두 데이터 값의 목록을 비교하고이를 모두 정렬 된 순서로 배치하는 발견 된 데이터 값 목록으로 병합합니다.
최종 병합 후 목록은 다음과 같아야합니다.
이제 우리는 병합 정렬의 몇 가지 프로그래밍 측면을 배워야합니다.
연산
병합 정렬은 목록을 더 이상 나눌 수 없을 때까지 동일한 절반으로 계속 나눕니다. 정의에 따라 목록에서 하나의 요소 만 있으면 정렬됩니다. 그런 다음 병합 정렬은 작은 정렬 목록을 결합하여 새 목록도 정렬합니다.
Step 1 − if it is only one element in the list it is already sorted, return.
Step 2 − divide the list recursively into two halves until it can no more be divided.
Step 3 − merge the smaller lists into new list in sorted order.의사 코드
이제 병합 정렬 기능에 대한 의사 코드를 살펴 보겠습니다. 우리의 알고리즘은 나누기와 병합이라는 두 가지 주요 기능을 지적합니다.
병합 정렬은 재귀와 함께 작동하며 동일한 방식으로 구현을 볼 것입니다.
procedure mergesort( var a as array )
if ( n == 1 ) return a
var l1 as array = a[0] ... a[n/2]
var l2 as array = a[n/2+1] ... a[n]
l1 = mergesort( l1 )
l2 = mergesort( l2 )
return merge( l1, l2 )
end procedure
procedure merge( var a as array, var b as array )
var c as array
while ( a and b have elements )
if ( a[0] > b[0] )
add b[0] to the end of c
remove b[0] from b
else
add a[0] to the end of c
remove a[0] from a
end if
end while
while ( a has elements )
add a[0] to the end of c
remove a[0] from a
end while
while ( b has elements )
add b[0] to the end of c
remove b[0] from b
end while
return c
end procedureC 프로그래밍 언어의 병합 정렬 구현에 대해 알아 보려면 여기 를 클릭하십시오 .