최악의 경우 선형시간 선택 구현 및 테스트

  최악의 경우 선형시간 선택 

최악의 경우에도 선택 알고리즘의 수행 시간이 Θ(n)이 되는 것을 보장하는 선택 알고리즘이다.

 

쉽게 배우는 알고리즘 선택 알고리즘 그림 4-3

 

최악의 경우 선형시간 선택 알고리즘

분할 알고리즘으로 배열을 n개 씩의 그룹으로 나누고 그룹의 중간 값들의 중간 값을 이용해 선택 알고리즘을 수행한다.

 

최악의 경우 선형시간 선택 알고리즘

LinearSelect(A[], p, r, i)
{
    1. 원소의 총 수가 5개 이하이면 원하는 원소를 찾고 알고리즘을 끝낸다.
    2. 전체 원소를 5개씩의 원소를 가진 ┌n/5┐개의 그룹으로 나눈다.
    3. 각 그룹에서 중앙값을 찾는다.
    	+ 이렇게 찾은 중앙값들을 m1, m2,..., m┌n/5┐이라 하자.
    4. m1, m2,..., m┌n/5┐들의 중앙값 m을 재귀적으로 구한다.
    5. M을 기준 원소로 삼아 전체 원소를 분할한다.
    6. 분할된 두 그룹 중 적합한 쪽을 선택해 단계 1~6을 재귀적으로 반복한다.
}

 

최악의 경우 선형시간 선택 구현

배열 arr과 배열의 길이 n, 원하는 순서 idx를 입력으로 받는 함수를 구현한다.

 

LinearSelection.hpp

#pragma once
#include "../Common.h"
#include "AvgNSelection.hpp"

int LinearSelection(int arr[], int midArr[], int p, int r, int idx);
int GetMidValue(int arr[], int midArr[], int p, int r);
int Partition(int arr[], int p, int r, int midValue);

/// <summary>
/// 주어진 배열에서 idx 번째로 작은 값을 찾는다.
/// </summary>
/// <param name="arr">정렬을 진행할 배열</param>
/// <param name="n">배열의 길이</param>
/// <param name="target">찾으려는 값</param>
/// <param name="printData">결과 출력 여부</param>
void LinearSelection(int arr[], int n, int idx, bool printData = false)
{
	int midArrCount = (n / 5) + 1;
	int* midArr = new int[midArrCount];

	int result{ LinearSelection(arr, midArr, 0, n - 1, idx) };

	if (printData)
	{
		std::cout << result << '\n';
	}

	delete[] midArr;
}

/// <summary>
/// 주어진 배열에서 idx 번째로 작은 값을 찾는다.
/// </summary>
/// <param name="arr">정렬을 진행할 배열</param>
/// <param name="p">배열의 시작 인덱스</param>
/// <param name="r">배열의 끝 인덱스</param>
/// <param name="target">찾으려는 값</param>
int LinearSelection(int arr[], int midArr[], int p, int r, int idx)
{
	if (p - r < 5)
	{
		return AvgNSelection(arr, p, r, idx);
	}

	int q{ Partition(arr, p, r, GetMidValue(arr, midArr, p, r)) };
	int k{ q - p + 1 };
	if (idx < k)
	{
		return LinearSelection(arr, midArr, p, q - 1, idx);
	}
	else if (idx == k)
	{
		return arr[q];
	}
	else
	{
		return LinearSelection(arr, midArr, q + 1, r, idx - k);
	}
}

/// <summary>
/// 중간 값을 찾아 반환한다.
/// </summary>
/// <param name="arr">전체 배열</param>
/// <param name="midArr">중간 값 저장 배열</param>
/// <param name="p">배열의 시작 인덱스</param>
/// <param name="r">배열의 끝 인덱스</param>
/// <returns>중간 값</returns>
int GetMidValue(int arr[], int midArr[], int p, int r)
{
	int midIdx{ 0 };
	int midTempArr[5];
	for (int i = p; i <= r;)
	{
		int j = 0;
		for (; j < 5 && i <= r; j++, i++)
		{
			midTempArr[j] = arr[i];
		}

		midArr[midIdx++] = AvgNSelection(midTempArr, 0, j - 1, 3);
	}

	return AvgNSelection(midTempArr, 0, midIdx - 1, midIdx / 2);
}

/// <summary>
/// 주어진 배열을 끝 값 기준으로 나눈다.
/// </summary>
/// <param name="arr">정렬을 진행할 배열</param>
/// <param name="p">배열의 시작 인덱스</param>
/// <param name="r">배열의 끝 인덱스</param>
int Partition(int arr[], int p, int r, int midValue)
{
	int i{ p }, j{ p };
	int midValueIdx{ p };
	while (i < r && j < r)
	{
		if (arr[j] == midValue)
		{
			midValueIdx = j++;
			continue;
		}

		if (arr[j++] < midValue)
		{
			Common::Swap(arr, i, j - 1);
			i++;
		}
	}
	Common::Swap(arr, i, midValueIdx);

	return i;
}

 

난수 1,000,000개에 대한 수행 시간은 다음과 같다.

total time is 0s ( 8ms )

 

NadanKim/Algorithm: 알고리즘 학습 및 예제 코드 작성을 위한 저장소 (github.com)

NadanKim/Algorithm

 

참고문헌

한빛아카데미.문병로.(2016.07.24).쉽게 배우는 알고리즘