수 정렬하기2 (2751)

1. 문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

첫째 줄에 수의 개수 N(1<=N<=1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절대값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

2. 포인트

1) 입력 갯수가 많으므로 O(2^N) 정렬 알고리즘으로 불가

   따라서, 조금 더 빠른 O(N*logN) 정렬 알고리즘 선택 → 합병 정렬(재귀) 선택!

2) 동적할당 포인터 배열 크기

- sizeof(sortArr) : 4

* 배열 이름의 경우는 sizeof 연산자가 배열 전체 크기를 반환해줌

  하지만, 동적할당한 경우는 그저 포인터일 뿐이므로(배열인지 그냥 포인터인지 알 수 없음) 포인터 자체 크기만 반환해줌

3. 소스코드

#include <stdio.h>

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

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

int main()

{

int tCase, temp;

int i, j;

int *arr;

scanf("%d", &tCase);

arr = (int*)malloc(sizeof(int)*tCase);

for (i = 0; i < tCase; i++)

{

scanf("%d", &temp);

arr[i] = temp;

}

MergeSort(arr, 0, tCase -1);

// tCase -1 값 말고 처음에 동적할당된 배열 크기 구하기 위해 sizeof(arr) / sizeof(int) 로 구하려 했더니 1이 나왔음..

for (i = 0; i < tCase; i++)

printf("%d\n", arr[i]);

return 0;

}

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

{

int mid = (left + right) / 2;

if (left < right)

{

MergeSort(arr, left, mid);

MergeSort(arr, mid+1, right);

MergeTwoArea(arr, left, mid, right);

}

}

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

{

int sIdx = 0, i;

int fIdx = left, rIdx = mid + 1;

int *sortArr = (int*)malloc(sizeof(int)*((right-left)+1));

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];

}

sIdx = 0;

for (i = left; i <= right; i++, sIdx++)

arr[i] = sortArr[sIdx];

free(sortArr);

}