존 폰 노이만(John von Neumann) 이 만든 분할 정복 알고리즘
Devide, Conquer, Combine
1. 분할(홀수일경우)
2. 병합 (Merge)
분할(짝수일경우)
#include<stdio.h>
#define SIZE 8
int tmp[SIZE];
void merge(int arr[], int left, int right)
{
int L, R, k, a;
int mid = (left + right) / 2;
L = left;
R = mid + 1;
k = left;
while (L<=mid&&R<=right)
{
tmp[k++] = arr[L] <= arr[R] ? arr[L++] : arr[R++];
}
if (L > mid)
{
for (a = R; a <= right; a++)
{
tmp[k++] = arr[a];
}
}
else
{
for (a = L; a <= mid; a++)
{
tmp[k++] = arr[a];
}
}
for (a = left; a <= right; a++)
{
arr[a] = tmp[a];
}
}
void mergeSort(int arr[], int left, int right)
{
if (left == right)return;
int mid;
mid = (left + right) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, right);
}
int main()
{
int arr[SIZE] = { 7,6,5,8,3,5,9,1 };
mergeSort(arr, 0, SIZE - 1);
for (int i = 0; i < SIZE;i++)
{
printf("%d", arr[i]);
}
}
'알고리즘' 카테고리의 다른 글
힙정렬(heap sort) (0) | 2021.01.13 |
---|---|
쉘 정렬(Shell sort) (0) | 2020.11.10 |
퀵정렬(Quick Sort) (0) | 2020.11.05 |
삽입정렬(insertion sort) (0) | 2020.10.21 |
선택정렬(selection sort) (0) | 2020.09.18 |
댓글