5개의 수에서 중앙값 찾기 (Median Selection)

5개의 수에서 6번의 비교로 중앙값을 찾는 알고리즘을 알아보자.

이 방법은 Selection algorithm의 토대가 된다.

 

알고리즘 (C++)

int median(int list[5])
{
	int w1, l1, w2, l2;

	if (list[0] > list[1])
	{
		w1 = list[0];
		l1 = list[1];
	}
	else
	{
		w1 = list[1];
		l1 = list[0];
	}

	if (list[2] > list[3])
	{
		w2 = list[2];
		l2 = list[3];
	}
	else
	{
		w2 = list[3];
		l2 = list[2];
	}

	if (w1 > w2)
	{
		if (list[4] > l1)
			w1 = list[4];
		else
		{
			w1 = l1;
			l1 = list[4];
		}
	}
	else
	{
		if (list[4] > l2)
			w2 = list[4];
		else
		{
			w2 = l2;
			l2 = list[4];
		}
	}

	if (w1 > w2)
		return (w2 > l1) ? w2 : l1;
	else
		return (w1 > l2) ? w1 : l2;
}

 

1. 4개의 값을 토너먼트 형식으로 비교하여 최댓값을 구한다. 이 값은 중앙값이 될 수 없다. (이 과정에서 3번의 비교가 필요하다.)
2. 1.에서 사용되지 않은 나머지 한 값을 1.에서의 최댓값 자리에 넣고, 4개의 값을 토너먼트 형식으로 비교하여 최댓값을 구한다. 이 값은 중앙값이 될 수 없다. (이 과정에서 2번의 비교가 필요하다.)
3. 남은 세 숫자 중 최댓값을 구한다. 이 값이 중앙값이다. (이 과정에서 1번의 비교가 필요하다.)

위의 방법에 따라, 총 6번의 비교로 중앙값을 구할 수 있다.

 

추가: 중앙값 정렬하기

위의 알고리즘을 바탕으로 5개의 수를 정렬해보자. 이때, 여기서의 정렬은 완벽한 정렬이 아니라, 오로지 (중앙값보다 작은 값), (중앙값), (중앙값보다 큰 값) 순으로만 정렬하는 것이다.

 

#define SWAP(a, b, temp) (temp = a, a = b, b = temp)
void set_median(int list[5])
{
	int temp;

	// set to: list[1] > list[2]
	if (list[1] < list[2])
		SWAP(list[1], list[2], temp);

	// set to: list[3] > list[4]
	if (list[3] < list[4])
		SWAP(list[3], list[4], temp);

	// set to list[0] is bigger than median
	if (list[1] > list[3])
	{
		SWAP(list[0], list[1], temp);
		if (list[1] < list[2])
			SWAP(list[1], list[2], temp);
	}
	else
	{
		SWAP(list[0], list[3], temp);
		if (list[3] < list[4])
			SWAP(list[3], list[4], temp);
	}

	if (list[1] > list[3])
	{
		if (list[2] < list[3])
			SWAP(list[2], list[3], temp);
	}
	else
	{
		SWAP(list[1], list[3], temp);
		if (list[3] > list[4])
			SWAP(list[2], list[3], temp);
		else
			SWAP(list[2], list[4], temp);
	}
}

위 코드를 기반으로 Median of Medians를 구하는 코드를 작성할 수도 있을 것이다.