(p93) k 길 병합

병합 정렬 과 마찬가지 로 k 길 은 약간 복잡 합 니 다. 하나의 최소 더미 (tmp) 로 모든 질서 있 는 배열 (result) 의 남 은 첫 번 째 요소 의 최소 값 을 유지 하고 결과 배열 에 추가 합 니 다. 더 미 는 지침 을 조작 하기 때문에 하나의 수 를 꺼 내지 않 고 지침 을 다음 요 소 를 가리 키 면 됩 니 다.(한 배열 의 요 소 를 다 취 했 는 지 판단 하기 위해 각 배열 뒤에 최대 값 32767 을 추가 하 였 습 니 다) 코드 는 다음 과 같 습 니 다.
/*
 * sort.c
 *
 *  Created on: Feb 13, 2016
 *      Author: wing
 */
#include<stdio.h>
#include<stdlib.h>
struct line{
	int l;
	int r;
};
int exchange(struct line *x,int i,int j)
{
	struct line tmp;
	tmp=x[i];
	x[i]=x[j];
	x[j]=tmp;
	return 0;
}
int sort(struct line *x,int l,int r)
{
	int i=l-1,j,k=l-1;
	if (r<=l) return 0;
	for (j=l;j<=r-1;j++)
		if (x[j].r<x[r].l)
		{
			exchange(x,k+1,i+1);
			exchange(x,k+1,j);
			i++;
			k++;
		}
		else
			if (x[j].l<=x[r].r)
			{
				exchange(x,i+1,j);
				i++;
			}
	exchange(x, i + 1, r);
	i++;
	sort(x,l,k);
	sort(x,i+1,r);
	return 0;
}
int main(void)
{
	int n,i;
	struct line *x;
	scanf("%d",&n);
	x=(struct line *)malloc(sizeof(struct line)*n);
	for (i=0;i<n;i++)
	{
		scanf("%d",&x[i].l);
		scanf("%d",&x[i].r);
	}
	sort(x,0,n-1);
	for (i=0;i<n;i++)
		printf("(%d,%d) ",x[i].l,x[i].r);
	return 0;
}

좋은 웹페이지 즐겨찾기