합병정렬은
4 3 2 1 9
이면 반으로 나눠서 정렬을 하고 다시 합치는 방법이다 그래서 쪼개는 과정이 재귀함수를 사용하면 된다.
4 3 2 / 1 9
4, 3, 2 서로 비교하게 되면
2 3 4가 된다
1, 9 서로 비교하게 되면
1 9 가 된다 .
--------------------------------------------------------------------------------------------
2 3 4 / 1 9
p q
p하고 q 비교
>> 1
---------------
2 3 4 / 1 9
p q
p하고 q 비교
>> 1 2
---------------
2 3 4 / 1 9
p q
p하고 q 비교
>> 1 2 3
---------------
2 3 4 / 1 9
p q
p하고 q 비교
>> 1 2 3 4
---------------
2 3 4 / 1 9
p q
p하고 q 비교
>> 1 2 3 4 9
----------------
만약 한쪽이 더 짧다면 왼쪽 전부를 넣어 주면 된다.
#include <iostream>
using namespace std;
void merge(int arr[],int start1,int e1,int start2, int e2)
{
int s1 = start1;
int s2 = start2;
int temp[100];
int temp_index=0;
while(s1 <= e1 && s2 <= e2)
{
if(arr[s1]>=arr[s2])
{
temp[temp_index]=arr[s1];
s1++;
}else{
temp[temp_index]=arr[s2];
s2++;
}
temp_index++;
}
//rest things put in arry
if(s1 > e1){ //rest s1 part
for(int i=s2;i<=e2;i++)
temp[temp_index++] = arr[i];
//굉장히 착각한 부분이다. s1 이 커진다고 해서
}else{
for(int i=s1;i<=e1;i++)
temp[temp_index++] = arr[i];
}
for(int i = start1;i<=e2;i++)
arr[i]=temp[i-start1];
}
void mergeSort(int arr[],int start, int end)
{
if(start >= end)
return;
else{
int mid = (start+end)/2;
mergeSort(arr,start,mid);
mergeSort(arr,mid+1,end);
merge(arr,start,mid,mid+1,end);
}
}
int main()
{
int arry[30];
int num;
cin >>num;
for(int i =0;i<num;i++)
cin >>arry[i];
mergeSort(arry,0,num-1);
for(int i =0;i<num;i++)
cout<< arry[i]<< " ";
return 0;
}
2가지 주의 사항 !!!!!
1. if(s1 > e1){ //rest s1 part
for(int i=s2;i<=e2;i++)
temp[temp_index++] = arr[i];
s1이 e1보다 크다는 것은 왼쪽으로 커지는 s1의 위치가 e1 보다 왼쪽에 있다는 것이 아니고 오른쪽에 있다는 것이다. !!!!!
>> 이상하게 나는 > 표시가 왼쪽에 있다로 보였다.
2. void merge(int arr[],int start1,int e1,int start2, int e2)
{
int s1 = start1;
int s2 = start2;
start1, start2 를 따로 빼놔야 다시 전체 값을 넣을때 이용할수 있다.
따로 빼놓지 않으면 이미 변경된 위치때문에 같은 값이 계속 들어가게 된다.
댓글