C 백준 2751 수 정렬하기 2 (정렬)

 

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

 

틀렸던 건데 다시 풀어봅니다

 

예전에 풀었을 때 계속 시간 초과 떴으니까 이 부분을 고치면 되지 않을까 싶음...

 

---

문제

1. 첫째 줄에 수 N(1 <= N <= 1000000) 입력
2. 둘째 줄에 첫째 줄에 입력한 수만큼 숫자 입력.
3. 오름차순 정렬
4. ★시간복잡도를 O(nlogn)★

---

#include <stdio.h>

void quickSort(int array[], int low, int high) {
	int L = low, H = high;
	if (high < 1) return; //원소 개수가 1개면 바로 출력함

	int pivot = array[(low + high) / 2]; 	//가운데 원소를  기준원소로 삼음

	while (low <= high) {
		while (array[low] < pivot) low++; //기준원소보다 low원소가 작을 때 low를 증가시킨다
		while (array[high] > pivot) high--; //기준원소보다 high원소가 클 때 high를 감소시킨다
		if (low <= high) {
			int tmp = array[low];			//원소를 교환시킨다
			array[low] = array[high];
			array[high] = tmp;
			low++;
			high--;
		}
	} while (low <= high);

	//재귀
	if (L < high)
		quickSort(array, L, high); //왼쪽 배열 재귀

	if (low < H)
		quickSort(array, low, H); //오른쪽 배열 재귀

}

int main(void) {
	int n = 0;
	int arr[1000000];

	scanf_s("%d", &n);

	for (int i = 0; i < n; i++) {
		scanf_s("%d", &arr[i]);
	}

	quickSort(arr, 0, n-1);

	for (int i = 0; i < n; i++) {
		printf("%d\n", arr[i]);
	}
	return 0;
}

예전에 만들었던 퀵정렬 알고리즘 수정해서 넣어봤음
그런데도 안됨

계속 시간 초과가 뜨는데 아마 퀵정렬이 최악의 경우 O(n²)이기 때문일까 싶다 ㄱ-
비주얼스튜디오에서도 스택오버플로우가 계속 뜨길래

프로젝트 속성에서 스택을 키우면 문제가 안 난대서 키워놨더니 프로그램에서는 잘 돌아갔다.
진짜 속상하다...

문제는 해결하고 싶어서 이번엔 merge sort를 이용해서 풀기로 했다.

merge sort는 평균 최악 전부 O(nlogn)인 알고리즘이다.

최종 코드

#include <stdio.h>
int temp[1000000] = {}; // 병합에 필요한 임시 배열

void merge(int array[], int low, int mid, int high) {

	int L, M, H;
	L = low;
	M = mid + 1;
	H = low;

	// 배열을 정렬
	while (L <= mid && M <= high) {
		if (array[L] <= array[M])
			temp[H++] = array[L++];
		else
			temp[H++] = array[M++];
	}

	// 두 배열 병합
	if (L > mid) {
		for (int i = M; i <= high; i++)
			temp[H++] = array[i];
	}
	else {
		for (int i = L; i <= mid; i++)
			temp[H++] = array[i];
	}

	
	for (int i = low; i <= high; i++) {// 임시배열을 원래에 배열로 복사
		array[i] = temp[i];
	}
}

void merge_sort(int array[], int low, int high) {
	if (low < high) {
		int mid = (low + high) / 2;  // 중간을 기준으로 리스트 분할
		merge_sort(array, low, mid); // 앞 리스트 정렬
		merge_sort(array, mid + 1, high); // 뒤 리스트 정렬
		merge(array, low, mid, high); // 정렬된 배열 병합
	}
}

int main(void) {
	int n = 0;
	int arr[1000000];

	scanf_s("%d", &n);

	for (int i = 0; i < n; i++) {
		scanf_s("%d", &arr[i]);
	}

	merge_sort(arr, 0, n-1);

	for (int i = 0; i < n; i++) {
		printf("%d\n", arr[i]);
	}
	return 0;
}

main 소스는 함수 사용 부분만 변경해서 그대로 사용.

merge_sort 함수 소스는 merge 부분을 어떻게 해야 될지 모르겠어서 이렇게 저렇게 해보다가 배열 정렬하는 부분에서 다른 사람의 힘을 조금 빌렸음... 전부 분리해서 합치는 과정 소스가 어려웠다.

[출처] https://airsbigdata.tistory.com/167

남들은 모르는 나만의 기나긴 싸움...
end............................
물론 다른 사람 도움을 받았지만...
해결했다는 게...
오늘 발 뻗고 자겠다.............

merge sort 알고리즘 분명히 아는데
코드로 짜려니까 잘 안됨......