선형 시간 선택

선형 시간 선택은 전체 정렬에서 n번째로 작은 원소를 찾을 때 사용할 수 있습니다.
전체 집합을 정렬하고 n번째 원소를 찾고자 한다면 $O (n l o g n)$ 시간이 소모 되겠지만 선형 시간 선택 알고리즘을 사용하면 $O (n)$ 의 시간으로 원소를 구할수 있습니다.
책을 기준으로

입력 버퍼를 5개의 원소를 가지는 부분 집합으로 나눕니다.
각각의 부분 집합들을 정렬합니다.
각각의 집합들에서 중앙값을 구하고, 중앙값들의 집합에서 또 중앙값을 찾습니다.
찾은 중앙값을 기준으로 두개의 벡터로 나눕니다.

1	1	3	4	4
2	2	4	5	6
3	4	7	8	8
1	1	9	23	30
	3	10	3

- 나누어진 벡터 중 피벗보다 원소값이 작은 원소의 집합의 사이즈+1의 값이 n과 같다면 찾고자한 값을 찾은 것이고,
- 집합의 사이즈+1의 값이 n보다 작다면 피벗보다 큰 원소값으로 구성된 집합을 가지고 1번 과정을 반복합니다.
- 집합의 사이즈+1의 값이 n보다 크다면 피벗보다 작은 원소값으로 구성된 집합을 가지고 1번 과정을 반복합니다.

다음은 선형 시간 선택의 코드입니다.

#include <iostream>
#include <vector>
using namespace std;
 
template<typename T>
auto partition(typename vector<T>::iterator begin, typename vector<T>::iterator end)
{
    auto pivot_val=*begin;
    auto left_iter=begin+1;
    auto right_iter=end;
    while (true)
    {
        while (*left_iter<=pivot_val&&distance(left_iter, right_iter)>0)
           left_iter++;
        while (*right_iter>pivot_val&&distance(left_iter, right_iter)>0)
           right_iter--;
        if(right_iter==left_iter)
            break;
        else
            iter_swap(left_iter, right_iter);
        
    }
    if(pivot_val>*right_iter)
        iter_swap(begin, right_iter);
 
    return right_iter;
}
 
template<typename T>
void quick_sort(typename vector<T>::iterator begin, typename std::vector<T>::iterator end)
{
    if(distance(begin, end)>=1)
    {
        auto partition_iter = partition<T>(begin, end);
        quick_sort<T>(begin, partition_iter-1);
        quick_sort<T>(partition_iter,end);
    }
}
 
template<typename T>
auto find_median(typename vector<T>::iterator begin, typename vector<T>::iterator last)
{
    quick_sort<T>(begin, last);
    return begin+(distance(begin, last)/2);
}
 
template<typename T>
auto partition_using_given_pivot(typename vector<T>::iterator begin, typename vector<T>::iterator end, typename vector<T>::iterator pivot)
{
    auto left_iter=begin;
    auto right_iter=end;
    while (true)
    {
        while(*left_iter<*pivot&&left_iter!=right_iter)
            left_iter++;
        while(*right_iter>=*pivot&&left_iter!=right_iter)
            right_iter--;
        if(left_iter==right_iter)
            break;
        else
            iter_swap(left_iter, right_iter);
    }
    if(*pivot>*right_iter)
        iter_swap(pivot, right_iter);
    return right_iter;
}
 
template<typename T>
typename vector<T>::iterator linear_time_select(typename vector<T>::iterator begin, typename vector<T>::iterator last, size_t i)
{
   auto size = distance(begin, last);
   if(size>0&&i<size)
   {
       auto num_Vi = (size+4)/5;
       size_t j =0;
 
       vector<T> M;
       for(;j<size/5;j++)
       {
           auto b=begin+(j*5);
           auto l=begin+(j*5)+5;
           M.push_back(*find_median<T>(b, l));
       }
       if(j*5<size)
       {
           auto b=begin+(j*5);
           auto l=begin+(j*5)+(size%5);
           M.push_back(*find_median<T>(b, l));
       }
       auto median_of_medians = (M.size()==1)?M.begin():linear_time_select<T>(M.begin(), M.end()-1, M.size()/2);
       auto partition_iter = partition_using_given_pivot<T>(begin, last, median_of_medians);
       auto k = distance(begin, partition_iter)+1;
       if(i==k)
           return partition_iter;
       else if(i<k)
           return linear_time_select<T>(begin, partition_iter-1, i);
       else
           return linear_time_select<T>(partition_iter+1, last, i-k);
    }
    else
    {
       return begin;
    }
}
 
template<typename T>
vector<T> merge(vector<T>& arr1, vector<T>& arr2)
{
    std::vector<T> merged;
    auto iter1 = arr1.begin();
    auto iter2 = arr2.begin();
    while(iter1!=arr1.end()&&iter2!=arr2.end())
    {
        if(*iter1<*iter2)
        {
            merged.emplace_back(*iter1);
            iter1++;
        }
        else
        {
            merged.emplace_back(*iter2);
            iter2++;
        }
    }
    if(iter1!=arr1.end())
    {
        for(;iter1!=arr1.end();iter1++)
            merged.emplace_back(*iter1);
    }
    else
    {
        for(;iter2!=arr2.end();iter2++)
            merged.emplace_back(*iter2);
    }
    return merged;
}
 
template<typename T>
vector<T> merge_sort(vector<T> arr)
{
    if(arr.size()>1)
    {
        auto mid=size_t(arr.size()/2);
        auto left_half = merge_sort(vector<T>(arr.begin(), arr.begin()+mid));
        auto right_half = merge_sort(vector<T>(arr.begin()+mid, arr.end()));
 
        return merge(left_half, right_half);
    }
    return arr;
}
 
template<typename T>
void print_vector(vector<T> arr)
{
	for (auto i : arr)
		cout << i << " ";
	cout << endl;
}
 
void run_linear_select_test()
{
    vector<int> S1{45, 1, 3, 1,2,3,45,5,1,2,44,5,7};
    cout<<"입력 벡터: "<<endl;
    print_vector<int>(S1);
    cout<<"정렬된 벡터: "<<endl;
    print_vector<int>(merge_sort<int>(S1));
    cout<<"3번째 원소"<<*linear_time_select<int>(S1.begin(), S1.end()-1, 3)<<endl;
    cout<<"5번째 원소"<<*linear_time_select<int>(S1.begin(), S1.end()-1, 5)<<endl;
    cout<<"11번째 원소"<<*linear_time_select<int>(S1.begin(), S1.end()-1, 11)<<endl;
}
 
int main()
{
    run_linear_select_test();
    return 0;
}

각각의 함수에 대한 간단한 설명을 하겠습니다.
1. auto find_median(typename vector<T>::iterator begin, typename vector<T>::iterator last)
해당 함수는 배열을 정렬한 후 배열의 중간 원소의 주소값을 반환하는 함수입니다.

2. auto partition_using_given_pivot(typename vector<T>::iterator begin, typename vector<T>::iterator end, typename vector<T>::iterator pivot)
해당 함수는 피벗을 기준으로 작은 값은 왼쪽으로, 큰 값은 오른쪽으로 옮기는, 이미 퀵 정렬에서 비슷한 개념을 한번 사용했었음, 함수입니다. 다만 배열 하나를 분할 하는 것이 아닌 전체 배열에서 중앙값을 찾은 후 그것을 피벗 삼아 분리하기에 전달인자가 한개 더 있습니다.

3. typename vector<T>::iterator linear_time_select(typename vector<T>::iterator begin, typename vector<T>::iterator last, size_t i)
해당 함수는 배열을 5개를 기준으로 나눈후 그 중앙값을 벡터 M에 저장한후 중간값의 중간 값을 찾고, 이를 피벗 삼아 분할하여, 피벗이 n번째 원소가 아니라면

피벗이 n보다 크다면 피벗보다 작은 원소들의 집합을 재귀 시키고,
피벗이 n보다 작다면 피벗보다 큰 원소들의 집합을 재귀시킵니다.
피벗과 n가 같을 때까지 과정을 반복합니다.

Bloodmoon

Bloodmoon

탐색기

선형 시간 선택

그래프 뷰