Sort Colors

• 한 쪽으로 Sorting 해서 몰아주는 것은 어떻게 해야할까?

1 0 2 2 0 1 2 1 0 -> 0 0 0 1 1 1 2 2 2

• 일반 Sort -> O(nlogn)
• Count Sort
  • O(n)의 전략
• In-place Swap으로 구현하라고 했을 때, 필요한 알고리즘이다.

Algorithm

1  0  2  2  0  1  2  1  0
p0p1                    p2

1  0  2  2  0  1  2  1  0
p0 p1					p2

0  1  2  2  0  1  2  1  0
   p0 p1                p2
  
0  1  0  2  0  1  2  1  2
   p0 p1             p2

• p0는 0을 찾는 pointer
• p1은 1을 찾는 pointer
• p2는 2를 찾는 pointer
• p1이 주체적으로 움직이는 pointer 라고 보면된다.
• p1은 0을 만나면 p0의 값과 바꿔주고, p0는 한칸 앞으로 전진한다.
• p1은 2를 만나면 p2의 값과 바꿔주고, p2는 한칸 뒤로 후진한다.
• p1과 p2가 엇갈렸다면, 종료한다.

Implementation

#include <iostream>
#include <vector>
#include <algorithm>

void sortColors(std::vector<int> &v)
{
    auto iter0 = v.begin();
    auto iter2 = v.end() - 1;
    auto iter1 = v.begin();

    while (iter1 <= iter2)
    {
        if (*iter1 == 0)
        {
            std::iter_swap(iter1, iter0);
            ++iter0;
        }
        else if (*iter1 == 2)
        {
            std::iter_swap(iter1, iter2);
            --iter2;
        }
        else
        {
            ++iter1;
        }
    }
}

int main()
{
    std::vector<int> v = {1, 0, 2, 2, 0, 1, 2, 1, 0};

    sortColors(v);

    for (int e : v)
        std::cout << e << " ";
    std::cout << std::endl;

    return 0;
}

0 0 0 1 1 1 2 2 2