평균 선형시간 선택 구현 및 테스트

  평균 선형시간 선택 

퀵 정렬의 분할 알고리즘을 이용하여 n 번째 원소를 빠르게 찾아내는 선택 방식이다.

 

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

 

평균 선형시간 선택 알고리즘

분할 알고리즘으로 두 개의 영역으로 나눈 뒤 n 번째 원소가 왼쪽에 포함되면 왼쪽 배열을 아니면 오른쪽 배열을 선택하는 과정을 반복하여 n 번째 원소를 찾는다.

 

평균 선형시간 선택 알고리즘

Select(A[], p, r, i)
{
    if (p = r) then
    {
        return A[p];
    }
    q ← Partition(A, p, r);
    k ← q - p + 1;
    if (i < k) then
    {
        return Select(A, p, q - 1, i);
    }
    else if (i = k) then
    {
        return A[q];
    }
    else
    {
        return Select(A, q + 1, r, i - k);
    }
}

 

평균 선형시간 선택 구현

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

 

AvgNSelection.hpp

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

int AvgNSelection(int arr[], int p, int r, int idx);
int Partition(int arr[], int p, int r);

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

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

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

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

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

	return i;
}

 

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

total time is 0s ( 9ms )

 

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

NadanKim/Algorithm

 

참고문헌

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