예제를 사용하여 C ++에서 병합 정렬을 구현하는 방법



이 기사는 C ++의 Merge Sort에 대한 세부적이고 포괄적 인 지식과 예제와 함께 작동하는 방법을 제공합니다.

병합 정렬이란 무엇입니까? 병합 정렬은 나누기 및 정복 범주에 속하는 비교 기반 정렬 알고리즘입니다. 병합 정렬은 분할 및 정복 전략을 기반으로 배열을 정렬하는 데 사용되며, 예제와 함께 알고리즘과 같은 다른 개념과 함께이 게시물에서 간략하게 다룹니다. 또한 C ++에서 병합 정렬의 시간 복잡도를 살펴 보겠습니다.

이 기사에서는 다음 사항을 다룰 것입니다.





C ++의 병합 정렬에 대한이 기사를 계속 진행합니다.

분할 및 정복 알고리즘

퀵 정렬이 어떻게 작동하는지 이미 알고 있다면 분할 및 정복 전략을 알고있을 것입니다. Divide and Conquer는 세 가지 주요 단계를 포함합니다. 이 단계를 이해하기 위해 시작 인덱스 'a'와 끝 인덱스 'n'이있는 배열 Hello []를 고려해 보겠습니다. 따라서 다음과 같은 방식으로 배열을 작성할 수 있습니다. Hello [a & hellip..n]



분할-분할 정복의 원동력 또는 주된 단계는 주어진 문제를 하위 문제 또는 하위 부분으로 나누는 것입니다. 여기서 문제는 하위 문제가 원래 문제와 유사하고 크기가 작아야한다는 것입니다. 우리의 경우 배열을 2 개로 나눌 것입니다. [a & hellip.m] [m + 1 & hellip..n] m은 a와 n 인덱스의 중간에 있습니다.

정복-일단 문제를 하위 문제로 나누는 작업이 완료되면. 우리는 이러한 하위 문제를 재귀 적으로 해결합니다.

결합-이 단계에서는 하위 문제의 모든 솔루션을 적절한 방식으로 결합합니다. 즉, 2 개의 다른 정렬 된 배열을 결합하여 하나의 정렬 된 배열을 형성합니다. 정렬 된 배열이 있습니다.



C ++의 병합 정렬에 대한이 기사를 계속 진행합니다.

예제를 통한 병합 정렬 알고리즘 이해

이 시점에서 우리는 병합 정렬에서 어떤 접근 방식을 사용할지 알고 있습니다. 따라서 예제를 고려하고 정렬되지 않은 Hello []에서 정렬 된 배열로 각 단계를 살펴 보겠습니다.
예-Hello [10, 3, 7, 1, 15, 14, 9, 22]

Merge-sort-in-C++

위 이미지에서 정렬되지 않은 배열을 고려하고 병합 정렬을 사용하여 정렬 된 배열을 얻었습니다. 이제 각 단계를 살펴보고 전체 알고리즘을 이해하겠습니다.

1. 먼저 배열 Hello [10, 3, 7, 1, 15, 14, 9, 22]를 고려했습니다.이 배열에는 총 8 개의 요소가 있습니다.

2. 앞에서 보았 듯이 병합 정렬은 분할 및 정복 접근 방식을 사용하여 요소를 정렬합니다. 우리는 배열의 중간에있는 m을 찾았고 중간에서 배열을 나눴습니다. .

3. 첫 번째 분할 후에는 각각 4 개의 요소로 구성된 2 개의 파트가 있습니다. 전반부 [10, 3, 7, 1]를 보겠습니다.

4. [10, 3, 7, 1]을 두 부분 [10, 3]과 [7, 1]로 나눕니다. 그런 다음 [10], [3], [7], [1]로 더 나눕니다. m을 계산할 수 없기 때문에 더 나눌 수 없습니다. 단일 요소를 포함하는 목록은 항상 정렬 된 것으로 간주됩니다.

5. 병합은 어떻게 이루어 집니까? 알아 보자. 먼저 [10]과 [3]은 [1, 7]과 같은 방식으로 오름차순 [3, 10]으로 비교되고 병합됩니다.

6. 그 후 [3, 10]과 [1, 7]을 비교합니다. 비교하면 오름차순으로 병합하고 [1, 3, 7, 10]을 얻습니다.

7. [15, 14, 9, 2]도 유사한 방식으로 분할되고 결합되어 [9, 14, 15, 22]를 형성합니다.

8. 마지막 단계에서 [15, 14, 9, 2] [9, 14, 15, 22]를 비교하고 결합하여 정렬 된 배열을 제공합니다.즉 [1, 3, 7, 9, 10, 14, 15, 22].

C ++의 병합 정렬에 대한이 기사를 계속 진행합니다.

병합 정렬을위한 의사 코드

왼쪽이면 시작

mergeSort () 함수는 단일 요소가 될 때까지 배열을 나누기 위해 자신을 재귀 적으로 호출하고 merge () 함수는 정렬 된 배열을 병합하는 데 사용됩니다.

C ++의 병합 정렬에 대한이 기사를 계속 진행합니다.

C ++에서 정렬 프로그램 병합

#include #include #include using namespace std void merge (int a [], int Firstindex, int m, int Lastindex) // 나눗셈 중에 생성 된 하위 배열을 병합합니다. void mergeSort (int a [], int Firstindex, int Lastindex) {if (Firstindexsize int Hello [size], i cout<<'Enter the elements of the array one by one:n' for(i=0 i>Hello [i] mergeSort (Hello, 0, size-1) cout<<'The Sorted List isn' for(i=0 i

산출-

C ++의 병합 정렬에 대한이 기사를 계속 진행합니다.

시간 복잡성

시간 복잡성은 알고리즘에 대해 이야기 할 때 고려해야 할 중요한 측면입니다. 병합 정렬은 다른 정렬 알고리즘에 비해 시간 복잡성이 큰 것으로 간주됩니다.

최악의 실행 시간-O (n log n)
최적의 실행 시간-O (n log n)
평균 실행 시간-O (n log n)

폭 우선 검색 알고리즘 의사 코드

이것으로 C ++의 Merge Sort 기사를 마칩니다. 자세한 내용은 다음을 확인하십시오. 신뢰할 수있는 온라인 학습 회사 인 Edureka에서 제공합니다. Edureka의 Java J2EE 및 SOA 교육 및 인증 과정은 Hibernate & Spring과 같은 다양한 Java 프레임 워크와 함께 핵심 및 고급 Java 개념 모두에 대해 교육하도록 설계되었습니다.

질문이 있으십니까? 이 블로그의 댓글 섹션에 언급 해 주시면 가능한 한 빨리 답변을 드리겠습니다.