[C] 백준 | 2751번 코드 - 수 정렬하기 2

>문제

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

 

[입력]

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

> 핵심

O(nlogn) 정렬방법 사용 / 중복처리

 

>풀이과정

합병정렬로 풀다가 merge 함수 부분에서 임시로 정렬된 값을 받을 tmp 배열을 calloc으로 할당하고 싶었는데

무슨 문제에선지 컴파일 에러가 자꾸 떴다. 할당 크기를 right가 아니라 (right + 1) 으로 하니 해결되었다.

 

그리고 qsort 함수 쓰니 정말 편하다. 앞으로도 애용해야겠다.

다만 주의해야 할게 형변환을 할때

int compare(const void* first, const void* second)
{
	if (*(int*)first > *(int*)second)
    	return 1;
        ..

이런식으로 *(int*)first, 앞에 *을 붙여줘야한다. 이거 빼먹었다가 정렬이 안돼서 뭐가 문제인가 해매다가 찾았다.

아니면 그냥 int *a = (int*)first 로 할당해놓고 *a 로 이용하면 괄호를 굳이 안써도 되니 비교하기에 더 직관적일 것 같다.

 

 

정렬 하는 김에 힙정렬도 간만에 해봤다. 간만에 하니 역시 어려웠다. 

1. 1부터 N까지 차례차례 힙 배열에 값을 넣는다(insert_Heap -> upHeap)

2. 반복문을 돌면서 선두 노드를 빼와서 (remove_Heap -> downHeap, 선두에 가장 큰 값이 있으니까)

3. 배열 가장 뒤에 배치(H.ar[H.n+1], H.n++가 아님에 유의) 하면서 정렬.

 

힙정렬은 전체 모든 수를 정렬할때 보다 상위 몇개의 수만 뽑아낼 때 더 유용하게 쓰인다고 한다.

알면 요긴하게 쓰겠지만 단점은 어렵다는 것..

 

>깨달은점

정렬은 기본이다 기본!

qsort 함수 굳

 

>코드

1. 합병정렬

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>


void merge(int list[], int left, int mid, int right)
{
	int i, j, k = 0;
	int* tmp = (int*)calloc(sizeof(int),(right + 1));
	i = left;
	j = mid + 1;

	while (i <= mid && j <= right)
	{
		if (list[i] <= list[j])
			tmp[k++] = list[i++];
		else
			tmp[k++] = list[j++];
	}
	while (i <= mid)
	{
		tmp[k++] = list[i++];
	}
	while (j <= right)
	{
		tmp[k++] = list[j++];
	}
	for (i = 0; i < k; i++)
	{
		list[i + left] = tmp[i];
	}
	free(tmp);
}

void merge_sort(int list[], int left, int right)
{
	int mid = (left + right) / 2;

	if (left < right)
	{
		merge_sort(list, left, mid);
		merge_sort(list, mid + 1, right);
		merge(list, left, mid, right);
	}
}

int main()
{
	int i, N, tmp, cnt;
	int* list;

	scanf("%d", &N);

	list = (int*)calloc(N, sizeof(int));

	for (i = 0, cnt = 0; i < N; i++)
	{
		scanf(" %d", &tmp);
		list[cnt++] = tmp;
	}

	merge_sort(list, 0, cnt - 1);

	for (i = 0; i < cnt; i++)
	{
		if (i != 0 && list[i] == list[i - 1])
		{
			i += 1;
			continue;
		}
		printf("%d ", list[i]);
	}

	free(list);

	return 0;
}

 

2. 퀵정렬 (qsort)

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

int compare(const void* first, const void* second)
{
	if (*(int*)first > *(int*)second)
		return 1;
	else if (*(int*)first < *(int*)second)
		return -1;
	else
		return 0;
}

int main()
{
	int i, N, tmp, cnt;
	int* list;

	scanf("%d", &N);

	list = (int*)calloc(N, sizeof(int));

	for (i = 0, cnt = 0; i < N; i++)
	{
		scanf(" %d", &tmp);
		list[cnt++] = tmp;
	}

	qsort(list, cnt, sizeof(list[0]), compare);

	for (i = 0; i < cnt; i++)
	{
		if (i != 0 && list[i] == list[i - 1])
		{
			i += 1;
			continue;
		}
		printf("%d ", list[i]);
	}

	free(list);

	return 0;
}

 

3. 힙정렬

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

typedef struct Heap {
	int *ar;
	int n;
}Heap;

void upHeap(Heap* H, int idx)
{
	if (idx <= 1) return;
	else
	{
		if (H->ar[idx / 2] <= H->ar[idx])
		{
			int tmp = H->ar[idx];
			H->ar[idx] = H->ar[idx / 2];
			H->ar[idx / 2] = tmp;
			upHeap(H, idx / 2);
		}
	}
}

void downHeap(Heap* H, int idx)
{
	if (idx * 2 > H->n) return;
	else
	{
		if (H->ar[idx * 2] > H->ar[idx] || H->ar[idx * 2 + 1] > H->ar[idx])
		{
			if (H->ar[idx * 2] > H->ar[idx * 2 + 1])
			{
				int tmp = H->ar[idx * 2];
				H->ar[idx * 2] = H->ar[idx];
				H->ar[idx] = tmp;
				downHeap(H, idx * 2);
			}
			else
			{
				int tmp = H->ar[idx * 2 + 1];
				H->ar[idx * 2 + 1] = H->ar[idx];
				H->ar[idx] = tmp;
				downHeap(H, idx * 2 + 1);
			}
		}
		else
			return;
	}
}

void insert_Heap(Heap *H, int value)
{
	H->ar[++H->n] = value;
	upHeap(H, H->n);
}

int remove_Heap(Heap* H)
{
	int value = H->ar[1];
	H->ar[1] = H->ar[H->n--];
	downHeap(H, 1);
	return value;
}

void inPlaceHeapSort(Heap* H)
{
	int size = H->n, key;

	for (int i = 0; i < size; i++)
	{
		key = remove_Heap(H);
		H->ar[H->n + 1] = key;
	}
	H->n = size;
}

int main()
{
	int i, N, tmp;
	Heap list; list.n = 0;

	scanf("%d", &N);

	list.ar = (int*)calloc(N, sizeof(int));

	for (i = 0; i < N; i++)
	{
		scanf("%d", &tmp);
		insert_Heap(&list, tmp);
	}

	inPlaceHeapSort(&list);

	for (i = 1; i <= list.n; i++)
	{
		printf("%d ", list.ar[i]);
	}

	return 0;
}