문제

코드

//Sort2
//2751
#include <stdio.h>
#include <stdlib.h>

void MergeTwoArea(int arr[],int left, int mid, int right)
{
    int fIdx = left;
    int rIdx = mid + 1;
    int i;
    
    int * sortArr = (int*)malloc(sizeof(int)*(right+1)); // 임시배열 생성
    int sIdx = left;
    
    while(fIdx<=mid && rIdx <= right)
    {
        if(arr[fIdx]<=arr[rIdx])
            sortArr[sIdx] = arr[fIdx++];
        else
            sortArr[sIdx] = arr[rIdx++];
        
        sIdx++;
    }
    
    if(fIdx>mid)
    {
        for(i=rIdx;i<=right;i++,sIdx++)
            sortArr[sIdx]=arr[i];
    }
    else
    {
        for(i=fIdx;i<=mid;i++,sIdx++)
            sortArr[sIdx]=arr[i];
    }
    for(i=left;i<=right;i++)
        arr[i] = sortArr[i];
    
    free(sortArr); //해제
}


void MergeSort(int arr[],int left,int right)
{
    int mid;
    
    if(left<right)
    {
        //check mid
        mid = (left+right)/2;
        
        // Divide
        MergeSort(arr, left, mid);
        MergeSort(arr, mid+1, right);
        
        //Merge
        MergeTwoArea(arr, left, mid, right);
    }
    
    
}


int main(void)
{
    int arr[1000000];
    int test;
    
    scanf("%d",&test);
    
    for(int i=0;i<test;i++)
    {
        scanf("%d",&arr[i]);
    }
    
    MergeSort(arr, 0, test-1);
    
    for(int i=0;i<test;i++)
    {
        printf("%d\n",arr[i]);
    }
    return 0;
}

해설

이제 자료구조 파트로오니깐 슬슬 코드길이가 길어진다..
버블...이런 빅오 엔제곱짜리는 이 문제의 조건을 달성할 수 없으니
힙,퀵,병합정렬을 활용하여야한다.

그 중 나는 병합정렬로 구현했다..!
구조는 윤성우열혈자료구조에서 배운 구조를 활용하였다

크게 3가지 함수로 나눠진다
1: 쪼개기함수
2: 병합함수
3: 메인함수

하나씩 소개하겠다.

void MergeTwoArea(int arr[],int left, int mid, int right)

void MergeTwoArea(int arr[],int left, int mid, int right)
{
    int fIdx = left;
    int rIdx = mid + 1;
    int i;
    int * sortArr = (int*)malloc(sizeof(int)*(right+1)); // 임시배열 생성
    int sIdx = left;
    
    while(fIdx<=mid && rIdx <= right)
    {
        if(arr[fIdx]<=arr[rIdx])
            sortArr[sIdx] = arr[fIdx++];
        else
            sortArr[sIdx] = arr[rIdx++];
        
        sIdx++;
    }
    
    if(fIdx>mid)
    {
        for(i=rIdx;i<=right;i++,sIdx++)
            sortArr[sIdx]=arr[i];
    }
    else
    {
        for(i=fIdx;i<=mid;i++,sIdx++)
            sortArr[sIdx]=arr[i];
    }
    for(i=left;i<=right;i++)
        arr[i] = sortArr[i];
    
    free(sortArr); //해제
}

fIdx = 쪼갠 배열의 왼쪽 배열 시작 인덱스
rIdx = 쪼갠 배열의 오른쪽 배열 시작 인덱스
sIdx = 새로할당한 배열의 시작점이다

그 이후 while문을 통해서 왼쪽 배열과 오른쪽 배열의 인덱스에 해당하는 값을 하나씩 비교해주며 새로 할당한 배열에 넣어주는 방식으로 진행된다.

그 후 한쪽 배열이 끝에 다달하면 두가지 케이스로 나눠진다

1. fIdx 가 mid+1 이 되는 경우
   -> 왼쪽 배열이 새로할당한 배열로 모두 들어가고 오른쪽 배열만 남아있는 상태이다.
2. rIdx = right +1 이 되는 경우
   -> 오른쪽 배열이 새로할당한 배열로 모두 들어가고 왼쪽 배열만 남아있는 상태이다.

그래서 while문이 끝나고 나면 if 문을 시작하여
남은 쪽 배열을 알아내고 그것을 이후 새로할당한 배열에 넣는 작업을 시작한다.

그 이후 새로할당한 배열을 기존 배열로 넣고 할당해제를 해준다 !

이것이 쪼개기 함수인데 !
이 이후
병합함수를 이제 소개하겠다

void MergeSort(int arr[],int left,int right)

void MergeSort(int arr[],int left,int right)
{
    int mid;
    
    if(left<right)
    {
        //check mid
        mid = (left+right)/2;
		
        //Merge
        MergeSort(arr, left, mid);
        MergeSort(arr, mid+1, right);
        
        // Divide
        MergeTwoArea(arr, left, mid, right);
    }
    
    
    
}

쪼개기함수보다 비교적 간단하다
왜냐하면 재귀를 썼기때문...크흑...
재귀적으로 함수를 분활정복 하고 병합하는 과정을 거친다..!

그 후

main 함수

int main(void)
{
    int arr[1000000];
    int test;
    
    scanf("%d",&test);
    
    for(int i=0;i<test;i++)
    {
        scanf("%d",&arr[i]);
    }
    
    MergeSort(arr, 0, test-1);
    
    for(int i=0;i<test;i++)
    {
        printf("%d\n",arr[i]);
    }
    return 0;
}

함수에 인자를 넣어주고!!! 출력하고 결론이다 !!

자료구조,,알고리즘 아자자