글 읽기 - C언어 합병정렬 비재귀형 코드입니다.

adfsfsf 3년 전 2

배열을 통해 트리를 구현해서 만든 코드입니다. 주석을 참고하시면 될 겁니다. 이게 정렬을 사용하는 문제들에 도전하시는 분들께 도움이 되길 바랍니다. 정렬 문제에 쓰지는 마시고요, 어느 정도 정렬을 할 줄 안다 하시는 분들께, 매번 코드를 새로 작성하기 힘드니 참고하시는 용도로 쓰라고 올리는 겁니다. merge함수는 문제마다 다르기 때문에 따로 올리지 않겠습니다.

루프 마지막에 트리의 -1번 인덱스를 확인하지만 에러가 발생하지 않기에 그대로 올립니다.

void mergeSort(int left, int right)//left는 정렬의 시작 지점, right는 정렬 끝 지점의 인덱스입니다.
{
	int check[500001][5];//트리 배열입니다. 0번은 분할 배열의 시작 지점, 1번은 끝 지점, 2번은 parent 노드의 인덱스, 3번은 leftChild 노드의 인덱스, 4번은 rightChild 노드의 인덱스입니다.
	int ind, mid, maxind;
	ind = 0;
	check[ind][0] = left;
	check[ind][1] = right;
	check[ind][2] = -1;
	maxind = 0;//트리를 저장하는 배열의 가장 마지막 값이 들어있는 곳의 인덱스
	while (ind >= 0)//루트 노드가 merge가 되면, 루트 노드의 parent로 지정한 -1번이 인덱스가 되고, 이 때 루프를 종료합니다.
	{
		if (check[ind][3] == -1)//leftChild가 merge가 되었다면
		{
			if (check[ind][4] == -1)//rightChild가 merge가 되었다면
			{
				mid = (check[ind][0] + check[ind][1]) / 2;
				merge(check[ind][0], mid, check[ind][1]);
                if (check[check[ind][2]][3] == ind)//현재 노드가 parent 노드의 leftChild인지 rightChild인지 확인합니다.
					check[check[ind][2]][3] = -1;
				else
					check[check[ind][2]][4] = -1;
				ind = check[ind][2];
			}
			else
			{
				ind = check[ind][4];
				continue;
			}
		}
		else if (check[ind][0] < check[ind][1])//새로운 노드를 트리에 추가합니다.
		{
			mid = (check[ind][0] + check[ind][1]) / 2;
			check[maxind+1][2] = ind;
			check[maxind + 1][1] = mid;
			check[ind][3] = maxind + 1;
			check[maxind+1][0] = check[ind][0];
			maxind++;
			check[maxind + 1][2] = ind;
			check[maxind + 1][1] = check[ind][1];
			check[ind][4] = maxind + 1;
			check[maxind + 1][0] = mid + 1;
			maxind++;
			ind = check[ind][3];
		}
		else//재귀형 mergeSort에서는 아무 동작도 안 하고 상위 재귀로 돌아가지만 비재귀형이라 부모 노드로 돌아가도록 해줘야 합니다.
		{
			if (check[check[ind][2]][3] == ind)
				check[check[ind][2]][3] = -1;
			else
				check[check[ind][2]][4] = -1;
			ind = check[ind][2];
		}
	}
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

C언어 합병정렬 비재귀형 코드입니다.

adfsfsf 3년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말