모드 커뮤니티


프로그래밍 일반

c언어 힙정렬 질문..

배고픈상어-효묘 2020.02.17 조회 수 47 추천 수 0

백준 2751번. 시간복잡도가 O(n*log(n)) 정렬을 쓰랍니다. 힙정렬이 nlogn이라길래 알고리즘 구현해봤는데  시간 초과가 뜨네요.. 뭔가 쓸때없는 연산을 했다는건데 어디가 잘못될 걸까요?

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;

#define FOR(i, n) for(int i = 0 ; i < n ; i++)
void heapSort(int *arr, int lo, int hi);
void hSort(int *arr, int root, int hi);
void downHeap(int *arr, int hi, int root, int c);
int partialSort(int *arr, int root, int hi);

int main() {
	srand((unsigned)time(NULL));
	int n;
	int *arr=NULL;
	cin >> n;
	arr = (int*)calloc(n, sizeof(*arr));

	FOR(i, n) {
		int k;
		cin >> k;
		arr[i] = k;
	}cout << endl;


	heapSort(arr, 0, n - 1);


	FOR(i, n) {
		cout << arr[i] << "\n";
	}
	return 0;
}
void heapSort(int *arr, int lo, int hi) {
	int last = hi;
	while (last > 0) {
		hSort(arr, lo, last);

		int tmp = arr[lo];
		arr[lo] = arr[last];
		arr[last] = tmp;


		--last;
	}
}

void hSort(int *arr, int root, int hi) {
	int r = root;
	int c1 = r * 2 + 1;
	int c2 = r * 2 + 2;
	//maxHeap 한 번만
	//downHeap
	if (r <= hi && c1 <= hi) {
		hSort(arr, c1, hi);
		hSort(arr, c2, hi);
		int c = partialSort(arr, r, hi);
		//왼쪽 자식과 바꾸면 c = 1, 우측 자식과 바꾸면 c = 2, outOfIndexRange이거나 안 바꾸면 c = 0
		//c값에 따라서 donwHeap을 하는 것임
		downHeap(arr, hi, r, c);
	}
}

void downHeap(int *arr, int hi, int root, int c) {
	if (c == 0)return;
	int r = root;
	int c1 = r * 2 + 1;
	int c2 = r * 2 + 2;
	if (c == 1 && c1<=hi) {
		int k = partialSort(arr, c1, hi);
		downHeap(arr, hi, c1, k);
	}
	else if(c==2 && c2<=hi){
		int k = partialSort(arr, c2, hi);
		downHeap(arr, hi, c2, k);
	}
}


int partialSort(int *arr, int root, int hi) {
	int r = root;
	int c1 = r * 2 + 1;
	int c2 = r * 2 + 2;
	//
	if (c2 > hi) {
		if (c1 > hi) {
			return 0;
		}else {
			if (arr[c1] > arr[r]) {
				int tmp = arr[r];
				arr[r] = arr[c1];
				arr[c1] = tmp;
				return 1;
			}
			else {
				return 0;
			}
		}
	}
	if (arr[c1] > arr[c2]) {
		if (arr[c1] > arr[r]) {
			int tmp = arr[r];
			arr[r] = arr[c1];
			arr[c1] = tmp;
			return 1;
		}
	}else if (arr[c2] > arr[r]) {
		int tmp = arr[r];
		arr[r] = arr[c2];
		arr[c2] = tmp;
		return 2;
	}
	return 0;
}

 




2개의 댓글

camelCase
2020.02.17

저라면 저거 코드 한줄한줄 읽기보다는 간단한 테스트 로직 짜서 IDE로 돌려볼것 같네요.

본인 컴퓨터에서 테스트 한번 해보세요

디버깅은 바텀업이아니라 탑다운으로 하는게 편합니다

@camelCase

작동은 합니다! 다만 시간초과가 걸릴뿐..ㅠ

질문

개발에 관련하여 궁금한 것들을 질문하는 공간입니다.

조회 수 제목 글쓴이
386 한디포 이용 규칙 15 초스터
621 한디포 이용 가이드! 처음 온 분은 읽어둡시다! 15 초스터
9007 한마포 AD 소개 (유료 광고 서비스) 55 프리루트
50 [시스템] 슬라임 점프 못하게 하는 법점 알려주세오 2 테크미
64 [스크립트] 스크립트 구문 질문.. 5 4nne_Marie
46 [스크립트] 스크립트 오류 3 marmotte
48 [플러그인] 랜덤 폭죽 발사가능하게하는 플러그인 제작하는거 어려울까요? 3 쿠로이츠바사
70 [프로그래밍 일반] 드랍 바꾸는 법 알려주세요 2 inecraft_player
98 [스크립트] 스코어보드에 코로나바이러스 현황 표시 4 inecraft_player
29 [스크립트] 스크립트 질문받아주실 선생님을 찾습니다 1 김솬
63 [스크립트] 야생 스크립트 질문있어요ㅜ 4 LowHoliC
67 [시스템] 스크립트? 플러그인? 9 hangan
96 [스크립트] 이런식으로 블럭이 계속 바뀌게 하는건 어떻게 하나요? 7 허윤
47 [프로그래밍 일반] c언어 힙정렬 질문.. 2 배고픈상어-효묘
60 [프로그래밍 일반] 파이썬 질문이여 3 레도
60 [스크립트] 스크립트 플러그인적용문제 3 허윤
83 [플러그인] 플러그인은 뭘로 배우면 좋나요?? 10 goodbye
149 [플러그인] 플레이어가 인벤토리를 열면 인식되게 어떻게하나요? 3 묘단

 

개발자 최신글
사진이 없습니다.

구인

1.5.2 서버 도와주실분 구합니다

사람사람사람인인사람인

2020-04-08

0

사진이 없습니다.

구인

JE[PC] 2020년 4월 한 섭관리자가 한마포에서 마인팜 서버 구인 글[건축가도 뽑아요!]을 쓰는데...... 과연 성공을 할 수 있을까? 여러분의 지원을 바랍니다!

드레

2020-04-08

0