C++에서 병합 정렬이란?

목차

• 소개
• C++에서 병합 정렬이란?
• 분할 정복 접근법
• 병합 정렬 알고리즘
• C++에서 병합 정렬 구현
• 결론

1. 소개

컴퓨터 과학의 정렬 알고리즘은 데이터를 오름차순 또는 내림차순으로 정렬하는 데 사용됩니다. 고유한 속성을 사용할 수 있는 여러 정렬 알고리즘이 있습니다. 병합 정렬은 배열을 정렬할 수 있는 C++의 방법 중 하나입니다.

2. C++에서 병합 정렬이란?

병합 정렬은 배열의 요소를 배열할 수 있는 분할 정복 기술을 사용합니다. 또한 C++에서 요소 목록을 정렬할 수도 있습니다. 입력을 두 부분으로 나누고 각 부분을 독립적으로 정렬한 다음 올바른 순서로 병합합니다.

3. 분할 정복 접근법

정렬 알고리즘은 입력 배열을 더 작은 하위 배열로 분할하고 개별적으로 해결한 다음 결과를 병합하여 정렬된 출력을 생성하는 분할 정복 전략을 적용합니다. 병합 정렬의 경우 배열은 각 절반에 하나의 요소만 남을 때까지 재귀적으로 두 개의 절반으로 나뉩니다.

4. 병합 정렬 알고리즘

병합 정렬 알고리즘은 분할 및 병합의 두 가지 주요 단계로 구성됩니다. 단계는 다음과 같습니다.

4.1 나누기

병합 정렬 알고리즘은 배열의 요소를 정렬하기 위한 분할 정복 전략을 따릅니다.

• 알고리즘의 첫 번째 단계는 배열 요소를 확인합니다. 하나의 요소를 포함하는 경우 이미 정렬된 것으로 간주되며 알고리즘은 변경 없이 동일한 배열을 반환합니다.
• 배열에 둘 이상의 요소가 포함된 경우 알고리즘은 배열을 왼쪽 절반과 오른쪽 절반의 두 부분으로 나눕니다.
• 병합 정렬 알고리즘은 배열의 왼쪽 및 오른쪽 절반에 재귀적으로 적용되어 효과적으로 더 작은 하위 배열로 나누고 개별적으로 정렬합니다.
• 이 재귀 프로세스는 하위 배열이 각각 하나의 요소만 포함할 때까지 계속되며(1단계에 따라) 최종 정렬된 출력 배열을 생성하기 위해 병합될 수 있습니다.

4.2 병합

이제 배열을 병합하는 단계를 볼 수 있습니다.

• 병합 정렬 알고리즘의 첫 번째 단계는 빈 배열을 만드는 것입니다.
• 그런 다음 알고리즘은 입력 배열의 왼쪽 및 오른쪽 절반의 첫 번째 요소를 비교합니다.
• 두 요소 중 더 작은 요소가 새 배열에 추가된 다음 입력 배열의 해당 절반에서 제거됩니다.
• 그런 다음 절반 중 하나가 비워질 때까지 2-3단계를 반복합니다.
• 비어 있지 않은 절반의 나머지 요소는 새 배열에 추가됩니다.
• 결과 배열은 이제 완전히 정렬되었으며 병합 정렬 알고리즘의 최종 출력을 나타냅니다.

5. C++에서 병합 정렬 구현

C++에서 병합 정렬을 구현하려면 두 가지 다른 방법을 따릅니다. 두 방법의 시간 복잡도는 동일하지만 임시 하위 배열의 사용법은 다릅니다.

C++의 병합 정렬에 대한 첫 번째 방법은 두 개의 임시 하위 배열을 사용하는 반면 두 번째 방법은 하나만 사용합니다. 첫 번째 방법의 두 임시 하위 배열의 총 크기가 두 번째 방법의 원래 배열 크기와 동일하므로 공간 복잡성이 일정하게 유지된다는 점은 주목할 가치가 있습니다.

• 방법 1 – 두 개의 임시 하위 배열 사용
• 방법 2 – 하나의 임시 하위 배열 사용

방법 1 – 두 개의 임시 하위 배열 사용

다음은 두 개의 임시 하위 배열을 사용하는 방법 1을 사용하는 C++의 병합 정렬에 대한 예제 프로그램입니다.

이 프로그램에서 병합 함수는 정렬할 배열을 나타내고 병합해야 하는 하위 배열의 인덱스를 나타내는 세 개의 인수 arr, l 및 r을 사용합니다. 함수는 먼저 병합할 두 하위 배열의 크기를 찾은 다음 이러한 하위 배열의 요소를 저장하기 위해 두 개의 임시 하위 배열 L 및 R을 만듭니다. 그런 다음 L과 R의 요소를 비교하고 이름이 지정된 원래 배열로 병합합니다. 알 오름차순으로.

분할 정복(divide-and-conquer) 기술은 mergeSort 함수에서 하위 배열에 하나의 요소만 남을 때까지 재귀적으로 배열을 두 개의 절반으로 분할하는 데 사용됩니다. 그런 다음 두 하위 배열을 정렬된 하위 배열로 병합합니다. 함수는 전체 배열을 정렬하지 않는 한 하위 배열을 계속 병합합니다.

main 함수에서 6개의 요소로 arr 배열을 정의하고 mergeSort 함수를 호출하여 정렬합니다. 코드 끝에 정렬된 배열이 인쇄됩니다.

방법 2 – 하나의 임시 하위 배열 사용

다음은 단일 임시 하위 배열을 사용하는 방법 2를 사용하는 C++의 병합 정렬에 대한 예제 프로그램입니다.

이 프로그램은 이전 프로그램과 같지만 두 개의 임시 하위 배열 L과 R을 사용하는 대신 단일 임시 하위 배열 temp를 사용합니다. 병합 기능은 기존과 동일하게 동작하지만 데이터를 L과 R에 복사하는 대신 temp에 복사합니다. 그런 다음 임시 배열 요소를 다시 알 원래 배열입니다.

mergeSort 함수는 임시 하위 배열을 저장하기 위해 L과 R 대신 temp를 사용한다는 점을 제외하면 이전과 동일합니다.

main 함수에서 6개의 요소로 arr 배열을 정의하고 mergeSort 함수를 호출하여 정렬합니다. 코드 실행은 정렬된 배열을 화면에 출력하면서 종료됩니다.

결론

병합 정렬은 배열 요소를 정렬하는 알고리즘으로, 분할 정복(divide-and-conquer) 기법을 사용하여 요소 간 비교를 수행합니다. C++의 병합 정렬은 O(n log n)의 시간 복잡도를 가지며 특히 큰 배열을 정렬하는 데 효과적입니다. 병합된 하위 배열을 저장하려면 추가 메모리가 필요하지만 안정성 때문에 정렬에 널리 사용됩니다.