Home-theater-designers
병합 정렬은 '나누고 정복' 기술을 기반으로 하는 정렬 알고리즘입니다. 가장 효율적인 정렬 알고리즘 중 하나입니다.
전화 수신을 중지하는 방법
이 기사에서는 병합 정렬 알고리즘의 작동, 병합 정렬 알고리즘, 시간 및 공간 복잡성, C++, Python 및 JavaScript와 같은 다양한 프로그래밍 언어에서의 구현에 대해 학습합니다.
병합 정렬 알고리즘은 어떻게 작동합니까?
병합 정렬은 분할 정복의 원칙에 따라 작동합니다. 병합 정렬은 각 하위 배열이 단일 요소로 구성될 때까지 배열을 두 개의 동일한 하위 배열로 반복적으로 나눕니다. 마지막으로 모든 하위 배열이 병합되어 결과 배열이 정렬됩니다.
이 개념은 예제를 통해 보다 효율적으로 설명할 수 있습니다. {16, 12, 15, 13, 19, 17, 11, 18} 요소가 있는 정렬되지 않은 배열을 고려하십시오.
여기에서 병합 정렬 알고리즘은 배열을 두 개의 절반으로 나누고 두 개의 절반에 대해 자신을 호출한 다음 정렬된 두 개의 절반을 병합합니다.
병합 정렬 알고리즘
다음은 병합 정렬 알고리즘입니다.
MergeSort(arr[], leftIndex, rightIndex)
if leftIndex >= rightIndex
return
else
Find the middle index that divides the array into two halves:
middleIndex = leftIndex + (rightIndex-leftIndex)/2
Call mergeSort() for the first half:
Call mergeSort(arr, leftIndex, middleIndex)
Call mergeSort() for the second half:
Call mergeSort(arr, middleIndex+1, rightIndex)
Merge the two halves sorted in step 2 and 3:
Call merge(arr, leftIndex, middleIndex, rightIndex)관련: 재귀란 무엇이며 어떻게 사용합니까?
병합 정렬 알고리즘의 시간 및 공간 복잡성
병합 정렬 알고리즘은 다음과 같은 반복 관계의 형태로 표현될 수 있습니다.
T(n) = 2T(n/2) + O(n)
마스터의 정리 또는 반복 트리 방법을 사용하여 이 반복 관계를 풀고 나면 솔루션을 O(n logn)으로 얻을 수 있습니다. 따라서 병합 정렬 알고리즘의 시간 복잡도는 오(n 로그인) .
병합 정렬의 최상의 시간 복잡도: O (n 로그인)
병합 정렬의 평균 시간 복잡도: 오(n 로그인)
병합 정렬의 최악의 경우 시간 복잡도: O (n 로그인)
관련된: Big-O 표기법이란 무엇입니까?
보조 공간 복잡성 병합 정렬 알고리즘의 에) 같이 N 병합 정렬 구현에는 보조 공간이 필요합니다.
병합 정렬 알고리즘의 C++ 구현
다음은 병합 정렬 알고리즘의 C++ 구현입니다.
// C++ implementation of the
// merge sort algorithm
#include
using namespace std;
// This function merges two subarrays of arr[]
// Left subarray: arr[leftIndex..middleIndex]
// Right subarray: arr[middleIndex+1..rightIndex]
void merge(int arr[], int leftIndex, int middleIndex, int rightIndex)
{
int leftSubarraySize = middleIndex - leftIndex + 1;
int rightSubarraySize = rightIndex - middleIndex;
// Create temporary arrays
int L[leftSubarraySize], R[rightSubarraySize];
// Copying data to temporary arrays L[] and R[]
for (int i = 0; i L[i] = arr[leftIndex + i];
for (int j = 0; j R[j] = arr[middleIndex + 1 + j];
// Merge the temporary arrays back into arr[leftIndex..rightIndex]
// Initial index of Left subarray
int i = 0;
// Initial index of Right subarray
int j = 0;
// Initial index of merged subarray
int k = leftIndex;
while (i {
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
// If there're some remaining elements in L[]
// Copy to arr[]
while (i {
arr[k] = L[i];
i++;
k++;
}
// If there're some remaining elements in R[]
// Copy to arr[]
while (j {
arr[k] = R[j];
j++;
k++;
}
}
void mergeSort(int arr[], int leftIndex, int rightIndex)
{
if(leftIndex >= rightIndex)
{
return;
}
int middleIndex = leftIndex + (rightIndex - leftIndex)/2;
mergeSort(arr, leftIndex, middleIndex);
mergeSort(arr, middleIndex+1, rightIndex);
merge(arr, leftIndex, middleIndex, rightIndex);
}
// Function to print the elements
// of the array
void printArray(int arr[], int size)
{
for (int i = 0; i {
cout << arr[i] << ' ';
}
cout << endl;
}
// Driver code
int main()
{
int arr[] = { 16, 12, 15, 13, 19, 17, 11, 18 };
int size = sizeof(arr) / sizeof(arr[0]);
cout << 'Unsorted array:' << endl;
printArray(arr, size);
mergeSort(arr, 0, size - 1);
cout << 'Sorted array:' << endl;
printArray(arr, size);
return 0;
} 산출:
Unsorted array:
16 12 15 13 19 17 11 18
Sorted array:
11 12 13 15 16 17 18 19병합 정렬 알고리즘의 JavaScript 구현
다음은 병합 정렬 알고리즘의 JavaScript 구현입니다.
// JavaScript implementation of the
// merge sort algorithm
// This function merges two subarrays of arr[]
// Left subarray: arr[leftIndex..middleIndex]
// Right subarray: arr[middleIndex+1..rightIndex]
function merge(arr, leftIndex, middleIndex, rightIndex) {
let leftSubarraySize = middleIndex - leftIndex + 1;
let rightSubarraySize = rightIndex - middleIndex;
// Create temporary arrays
var L = new Array(leftSubarraySize);
var R = new Array(rightSubarraySize);
// Copying data to temporary arrays L[] and R[]
for(let i = 0; i L[i] = arr[leftIndex + i];
}
for (let j = 0; j R[j] = arr[middleIndex + 1 + j];
}
// Merge the temporary arrays back into arr[leftIndex..rightIndex]
// Initial index of Left subarray
var i = 0;
// Initial index of Right subarray
var j = 0;
// Initial index of merged subarray
var k = leftIndex;
while (i {
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
// If there're some remaining elements in L[]
// Copy to arr[]
while (i {
arr[k] = L[i];
i++;
k++;
}
// If there're some remaining elements in R[]
// Copy to arr[]
while (j {
arr[k] = R[j];
j++;
k++;
}
}
function mergeSort(arr, leftIndex, rightIndex) {
if(leftIndex >= rightIndex) {
return
}
var middleIndex = leftIndex + parseInt((rightIndex - leftIndex)/2);
mergeSort(arr, leftIndex, middleIndex);
mergeSort(arr, middleIndex+1, rightIndex);
merge(arr, leftIndex, middleIndex, rightIndex);
}
// Function to print the elements
// of the array
function printArray(arr, size) {
for(let i = 0; i document.write(arr[i] + ' ');
}
document.write('
');
}
// Driver code:
var arr = [ 16, 12, 15, 13, 19, 17, 11, 18 ];
var size = arr.length;
document.write('Unsorted array:
');
printArray(arr, size);
mergeSort(arr, 0, size - 1);
document.write('Sorted array:
');
printArray(arr, size); 산출:
Unsorted array:
16 12 15 13 19 17 11 18
Sorted array:
11 12 13 15 16 17 18 19관련 항목: 동적 프로그래밍: 예제, 일반적인 문제 및 솔루션
병합 정렬 알고리즘의 Python 구현
다음은 병합 정렬 알고리즘의 Python 구현입니다.
# Python implementation of the
# merge sort algorithm
def mergeSort(arr):
if len(arr) > 1:
# Finding the middle index of the array
middleIndex = len(arr)//2
# Left half of the array
L = arr[:middleIndex]
# Right half of the array
R = arr[middleIndex:]
# Sorting the first half of the array
mergeSort(L)
# Sorting the second half of the array
mergeSort(R)
# Initial index of Left subarray
i = 0
# Initial index of Right subarray
j = 0
# Initial index of merged subarray
k = 0
# Copy data to temp arrays L[] and R[]
while i if L[i] arr[k] = L[i]
i = i + 1
else:
arr[k] = R[j]
j = j + 1
k = k + 1
# Checking if there're some remaining elements
while i arr[k] = L[i]
i = i + 1
k = k + 1
while j arr[k] = R[j]
j = j + 1
k = k + 1
# Function to print the elements
# of the array
def printArray(arr, size):
for i in range(size):
print(arr[i], end=' ')
print()
# Driver code
arr = [ 16, 12, 15, 13, 19, 17, 11, 18 ]
size = len(arr)
print('Unsorted array:')
printArray(arr, size)
mergeSort(arr)
print('Sorted array:')
printArray(arr, size)
산출:
Unsorted array:
16 12 15 13 19 17 11 18
Sorted array:
11 12 13 15 16 17 18 19다른 정렬 알고리즘 이해
정렬은 프로그래밍에서 가장 많이 사용되는 알고리즘 중 하나입니다. 퀵 정렬, 버블 정렬, 병합 정렬, 삽입 정렬 등과 같은 다양한 정렬 알고리즘을 사용하여 다양한 프로그래밍 언어로 요소를 정렬할 수 있습니다.
가장 간단한 정렬 알고리즘에 대해 배우고 싶다면 버블 정렬이 최선의 선택입니다.
공유하다 공유하다 트위터 이메일 버블 정렬 알고리즘 소개버블 정렬 알고리즘: 배열 정렬에 대한 훌륭한 소개입니다.
다음 읽기 관련 항목- 프로그램 작성
- 자바스크립트
- 파이썬
- 코딩 튜토리얼
Yuvraj는 인도 델리 대학교의 컴퓨터 공학 학부생입니다. 그는 풀 스택 웹 개발에 열정적입니다. 그는 글을 쓰지 않을 때 다양한 기술의 깊이를 탐구하고 있습니다.
유브라지 찬드라가 참여한 작품 더보기뉴스레터 구독
기술 팁, 리뷰, 무료 전자책 및 독점 거래에 대한 뉴스레터에 가입하십시오!
구독하려면 여기를 클릭하세요.