[백준] 2751번 : 수 정렬하기 2 (C언어 풀이)

https://www.acmicpc.net/problem/2751

2751번: 수 정렬하기 2

해당 문제는 수의 개수가 100만까지 있다. N^2로 하면 시간초과가 날게 뻔하다. 정렬 알고리즘 중에서 최대 NlogN까지의 시간복잡도를 갖는 애로 가야한다.

 

1) 퀵소트로 풀어봤다.

#include <stdio.h>

void quick (int arr[], int start, int end)
{
	if (start>=end)
    {
    	return;
    }
    
    int key = start;
    int i = start+1;
    int j = end;
    int change;
    
    while (i<=j)
    {
    	while (arr[key]<=arr[i])
        {
        	i++;
        }
        
        while (arr[j]>arr[key] && j>key)
        {
        	j--;
        }
        
        if (i>j)
        {
        	change = arr[j];
            arr[j] = arr[key];
            arr[key] = change;
        }
        
        else
        {
        	change = arr[j];
            arr[j] = arr[i];
            arr[i] = change;
        }
    }
    
    quick (arr,start,j-1);
    quick (arr,j+1,end);
}

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

근데 퀵소트로 푸니까 시간초과가 나왔다. 아마 퀵소트의 경우는 Best, Avg케이스는 NlogN이지만 Worst케이스는 N^2가 나올 수 있기 때문인 것 같다.

 

따라서, NlogN 정렬 중 합병정렬이나 힙 정렬로 접근해보고자 한다.

 

 

-> 합병정렬

#include <stdio.h>

int sorted[1000000];

void merge (int arr[], int start, int mid, int end)
{
	int i = start;
	int j = mid+1;
	int k = start;
	
	while(i<=mid && j<=end)
	{
		if (arr[i]<=arr[j])
		{
			sorted[k] = arr[i];
			i++;
		}
		else
		{
			sorted[k] = arr[j];
			j++;
		}
		k++;
	}
	
	if (i>mid)
	{
		int t;
		for (t=j; t<=end; t++)
		{
			sorted[k] = arr[t];
			k++;
		}
	}
	
	else
	{
		int t;
		for (t=start; t<=mid; t++)
		{
			sorted[k] = arr[t];
			k++;
		}
	}
	int t;
	for (t=start; t<=end; t++)
	{
		arr[t] = sorted[t];
	}
	
}

void merge_sort (int arr[], int start, int end)
{
	if (start<end)
	{
		int mid = (start+end)/2;
		merge_sort (arr,start,mid);
		merge_sort (arr,mid+1,end);
		merge (arr,start,mid,end);
	}
}

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