알고리즘 문제풀이/기본문제풀이
[기본문제풀이] merge_sort
로디네로
2020. 12. 27. 15:13
반응형
풀이 일시 : 2020-07-30
병합정렬 :
합병정렬 또는 병합정렬로 불린다. O(N*logN) 보장한다. 분할정복 알고리즘의 하나이다.
-> middle을 기준으로 반으로 나눈다. (이를 재귀형식으로 계속 나눈다.)
-> 나눈 것을 병합하며 정렬한다.
-> 병합하는 중 남은 데이터들이 있다면 나머지를 다 넣어주는 과정이 필요하다.
문제 :
76584591 을 오름차순으로 정렬하시오
#define number 8
#include<stdio.h>
int size;
int sorted[8];
int count = 0;
void merge(int a[], int m, int middle, int n) { //합칠 때 숫자를 비교하여 합치는 부분
int i = m; //첫번째 배열의 맨 앞
int j = middle + 1; //두번째 배열의 맨 앞
int k = m; //합쳐질 배열의 맨 앞
while (i <= middle && j <= n) { //범위를 넘지않는선에서
if (a[i] <= a[j]) {
sorted[k] = a[i]; //합쳐질 배열 저장공간 sorted
i++; //i를 다음칸으로 옮긴다.
}
else {
sorted[k] = a[j]; //sorted에 j값넣는다.
j++; //j도 다음칸으로 옮긴다.
}
k++; //k를 증가하면서 sorted배열을 완성해나가는거
}
//남은 데이터들도 삽입 (한쪽만 다 비었다면=범위넘었다면)
if (i > middle) { //i가 초과라면 j를 넣어줘야겠지
for (int t = j; t <= n; t++) {
sorted[k] = a[t];
k++;
}
}
else { //j가 초과라면 i를 넣어줘야겠지
for (int t = i; t <= middle; t++) {
sorted[k] = a[t];
k++;
}
}
//정렬된 배열을 다시 a[]에 삽입
for (int t = m; t <= n; t++) {
a[t] = sorted[t]; //sorted만들고 a배열 도출
}
}
void mergeSort(int a[],int m,int n) {
if (m < n) {
int middle = (m + n) / 2; //나눠주어 middle을 생성
mergeSort(a, m, middle); //앞 부분 재귀
mergeSort(a, middle + 1, n); //뒷 부분 재귀
merge(a, m, middle, n); //정렬한 후 merge를 수행한다.
//어떻게 sort를 수행하나면 끝까지 mergeSort로 쪼개면
//merge 부분에서 1 : 1 를 비교하게 됨
//a[i] <= a[j] 를 따지기 때문에 sort가 된다.
}
}
int main() {
int array[number] = { 7,6,5,8,3,5,9,1 };
mergeSort(array, 0, number - 1);
for (int i = 0; i < number; i++) {
printf("%d", array[i]);
}
}
반응형