merge sort c with examples
C ++ 병합 정렬 기법.
병합 정렬 알고리즘은“ 나누고 정복하다 ”문제를 하위 문제로 나누고 해당 하위 문제를 개별적으로 해결하는 전략입니다.
그런 다음 이러한 하위 문제를 결합하거나 병합하여 통합 솔루션을 구성합니다.
=> 여기에서 인기있는 C ++ 교육 시리즈를 읽어보십시오.
학습 내용 :
C ++ 실용적인 질문과 답변 pdf
개요
병합 정렬은 다음 단계를 사용하여 수행됩니다.
#1) 정렬 할 목록은 중간 요소의 목록을 나누어 길이가 같은 두 배열로 나뉩니다. 목록의 요소 수가 0 또는 1이면 목록이 정렬 된 것으로 간주됩니다.
#두) 각 하위 목록은 병합 정렬을 재귀 적으로 사용하여 개별적으로 정렬됩니다.
#삼) 그런 다음 정렬 된 하위 목록이 결합되거나 병합되어 완전한 정렬 목록을 형성합니다.
일반 알고리즘
병합 정렬 기술에 대한 일반적인 의사 코드는 다음과 같습니다.
길이가 N 인 배열 Arr 선언
N = 1이면 Arr이 이미 정렬되어 있습니다.
N> 1이면
왼쪽 = 0, 오른쪽 = N-1
중간 찾기 = (왼쪽 + 오른쪽) / 2
merge_sort (Arr, left, middle) => 전반을 재귀 적으로 정렬
merge_sort (Arr, middle + 1, right) => 후반부를 재귀 적으로 정렬합니다.
위 단계에서 정렬 된 배열을 병합하려면 merge (Arr, left, middle, right)를 호출하십시오.
출구
위의 의사 코드에서 볼 수 있듯이 병합 정렬 알고리즘에서는 배열을 반으로 나누고 병합 정렬을 재귀 적으로 사용하여 각 반을 정렬합니다. 하위 배열이 개별적으로 정렬되면 두 개의 하위 배열이 병합되어 완전한 정렬 배열을 형성합니다.
병합 정렬을위한 의사 코드
다음은 병합 정렬 기술에 대한 의사 코드입니다. 먼저 배열을 반복적으로 반으로 분할하는 절차 병합 정렬이 있습니다. 그런 다음 정렬 된 작은 배열을 병합하여 완전한 정렬 된 배열을 얻는 병합 루틴이 있습니다.
procedure mergesort( array,N ) array – list of elements to be sorted N – number of elements in the list begin if ( N == 1 ) return array var array1 as array = a(0) ... a(N/2) var array2 as array = a(N/2+1) ... a(N) array1 = mergesort(array1) array2 = mergesort(array2) return merge( array1, array2 ) end procedure procedure merge(array1, array2 ) array1 – first array array2 – second array begin var c as array while ( a and b have elements ) if ( array1(0) > array2(0) ) add array2 (0) to the end of c remove array2 (0) from array2 else add array1 (0) to the end of c remove array1 (0) from array1 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 procedure이제 병합 정렬 기술을 예제로 설명하겠습니다.
삽화
위의 그림은 아래 표 형식으로 표시 될 수 있습니다.
| 통과하다 | 정렬되지 않은 목록 | 나누기 | 정렬 된 목록 |
|---|---|---|---|
| 1 | {12, 23,2,43,51,35,19,4} | {12,23,2,43} {51,35,19,4} | {} |
| 두 | {12,23,2,43} {51,35,19,4} | {12.23} {2.43} {51.35} {19.4} | {} |
| 삼 | {12.23} {2.43} {51.35} {19.4} | {12.23} {2.43} {35.51} {4.19} | {12.23} {2.43} {35.51} {4.19} |
| 4 | {12.23} {2.43} {35.51} {4.19} | {2,12,23,43} {4,19,35,51} | {2,12,23,43} {4,19,35,51} |
| 5 | {2,12,23,43} {4,19,35,51} | {2,4,12,19,23,35,43,51} | {2,4,12,19,23,35,43,51} |
| 6 | {} | {} | {2,4,12,19,23,35,43,51} |
위의 표현에서 볼 수 있듯이, 먼저 배열은 길이 4의 두 개의 하위 배열로 나뉩니다. 각 하위 배열은 길이가 2 인 두 개의 하위 배열로 더 나뉩니다. 각 하위 배열은 추가로 하위 배열로 나뉩니다. 각각 한 요소의. 이 전체 프로세스가 '나누기'프로세스입니다.
배열을 각각 단일 요소의 하위 배열로 나누었 으면 이제 이러한 배열을 정렬 된 순서로 병합해야합니다.
위의 그림과 같이 단일 요소의 각 하위 배열을 고려하고 먼저 요소를 결합하여 정렬 된 순서로 두 요소의 하위 배열을 형성합니다. 다음으로, 길이가 2 인 정렬 된 하위 배열이 정렬되고 결합되어 길이가 각각 4 인 두 개의 하위 배열이 형성됩니다. 그런 다음이 두 하위 배열을 결합하여 완전한 정렬 배열을 형성합니다.
반복적 병합 정렬
위에서 본 병합 정렬의 알고리즘 또는 기술은 재귀를 사용합니다. 또한 ' 재귀 병합 정렬 ”.
재귀 함수는 함수 호출 스택을 사용하여 호출 함수의 중간 상태를 저장한다는 것을 알고 있습니다. 또한 매개 변수 등에 대한 기타 부기 정보를 저장하고 함수 호출의 활성화 기록을 저장하고 실행을 재개하는 측면에서 오버 헤드를 발생시킵니다.
재귀 함수 대신 반복 함수를 사용하면 이러한 모든 오버 헤드를 제거 할 수 있습니다. 위의 병합 정렬 알고리즘은 루프 및 의사 결정을 사용하여 반복 단계로 쉽게 변환 할 수도 있습니다.
재귀 적 병합 정렬과 마찬가지로 반복적 병합 정렬도 O (nlogn) 복잡도를 가지므로 성능면에서 서로 동등하게 수행됩니다. 우리는 단순히 오버 헤드를 낮출 수 있습니다.
이 튜토리얼에서는 재귀 적 병합 정렬에 중점을 두 었으며 다음으로 C ++ 및 Java 언어를 사용하여 재귀 적 병합 정렬을 구현합니다.
다음은 C ++를 사용한 병합 정렬 기술의 구현입니다.
#include using namespace std; void merge(int *,int, int , int ); void merge_sort(int *arr, int low, int high) { int mid; if (low num; cout<<'Enter '<myarray(i); } merge_sort(myarray, 0, num-1); cout<<'Sorted array
'; for (int i = 0; i < num; i++) { cout< 산출:
정렬 할 요소 수 입력 : 10
정렬 할 요소 10 개 입력 : 101 10 2 43 12 54 34 64 89 76
정렬 된 배열
2 10 12 34 43 54 64 76 89101
이 프로그램에서는 두 가지 기능을 정의했습니다. merge_sort 과 가다 . merge_sort 함수에서 배열을 두 개의 동일한 배열로 나누고 이러한 각 하위 배열에서 merge 함수를 호출합니다. 병합 기능에서 우리는 이러한 하위 배열에 대해 실제 정렬을 수행 한 다음 하나의 완전한 정렬 배열로 병합합니다.
다음으로, 우리는 Java 언어로 Merge Sort 기술을 구현합니다.
class MergeSort { void merge(int arr(), int beg, int mid, int end) { int left = mid - beg + 1; int right = end - mid; int Left_arr() = new int (left); int Right_arr() = new int (right); for (int i=0; i 산출:
입력 배열
101 10 2 43 12 54 34 64 89 76
병합 정렬을 사용하여 정렬 된 배열
2 10 12 34 43 54 64 76 89101
Java 구현에서도 C ++ 구현에서 사용한 것과 동일한 로직을 사용합니다.
병합 정렬은 목록을 정렬하는 효율적인 방법이며 대부분 연결 목록을 정렬하는 데 사용됩니다. 분할 및 정복 접근 방식을 사용하므로 병합 정렬 기술은 더 작은 배열과 더 큰 배열에 대해 똑같이 효율적으로 수행됩니다.
병합 정렬 알고리즘의 복잡성 분석
병합 정렬을 사용하여 정렬을 수행하려면 먼저 배열을 두 개의 동일한 절반으로 나눕니다. 이것은 로그 함수 인 'log n'으로 표시되며 수행 된 단계 수는 최대 log (n + 1)입니다.
다음으로 배열의 중간 요소를 찾으려면 단일 단계, 즉 O (1)이 필요합니다.
그런 다음 하위 배열을 n 요소의 배열로 병합하려면 O (n)의 실행 시간이 필요합니다.
따라서 병합 정렬을 수행하는 데 걸리는 총 시간은 n (log n + 1)이되며, 이는 O (n * logn)의 시간 복잡도를 제공합니다.
최악의 시간 복잡성 O (n * log n) 최상의 경우 시간 복잡성 O (n * log n) 평균 시간 복잡성 O (n * log n) 공간 복잡성 의 위에)
병합 정렬의 시간 복잡성은 항상 배열을 하위 배열로 나눈 다음 선형 시간을 사용하여 하위 배열을 병합하므로 세 가지 경우 (최악, 최고 및 평균) 모두에서 동일합니다.
병합 정렬은 항상 정렬되지 않은 배열과 동일한 공간을 차지합니다. 따라서 정렬 할 목록이 배열 인 경우 매우 큰 배열에는 병합 정렬을 사용하면 안됩니다. 그러나 병합 정렬은 연결 목록 정렬에 더 효과적으로 사용할 수 있습니다.
결론
병합 정렬은 배열 또는 목록을 여러 하위 배열로 나누고 개별적으로 정렬 한 다음 완전한 정렬 된 배열로 병합하는 '분할 및 정복'전략을 사용합니다.
병합 정렬은 다른 정렬 방법보다 빠르게 수행되며 더 작고 큰 배열에서도 효율적으로 작동합니다.
다음 튜토리얼에서 빠른 정렬에 대해 자세히 알아볼 것입니다!
=> 여기에서 초보자 C ++ 교육 가이드를 확인하십시오.
추천 도서