/*
**  Use Bucket Sort, it would only take O(n) times, but it go through array for twice
**
**  The second solution only go through array for once. This quesiton is named as "Dutch national flag problem"
**  Link: http://www.allisons.org/ll/AlgDS/Sort/Flag/
*/
#include <stdio.h>

void SortColors(int A[], int n) 
{
    int size[3] = {0, 0, 0};

    for (int i = 0; i < n; ++i)
        size[A[i]]++;
    
	size[1] += size[0];
	size[2] += size[1];
	int i = 0;
	
	while (i < size[0]) A[i++] = 0;
	while (i < size[1]) A[i++] = 1;
	while (i < size[2]) A[i++] = 2;
}

void Swap(int& a, int& b)
{
    int tmp = a;
    a = b;
    b = tmp;
}
//Invariant: a[1..Lo-1]=0 and a[Lo..Mid-1]=1 and a[Hi+1..N]=2; a[Mid..Hi] are unknown.
void ColorSort(int A[], int n)
{
    int low = 0;
    int high = n-1;
    while(low < n && A[low] == 0) ++low;
    while(high >= 0 && A[high] == 2) --high;

    int mid = low;
    while(mid <= high)
    {
        switch(A[mid])
        {
            case 0:
                Swap(A[mid], A[low]);
                ++low;
            case 1:
                ++mid;
                break;
            case 2:
                Swap(A[mid], A[high]);
                --high;
                break;
        }
    }
}

void PrintArray(int A[], int n)
{
    for (int i = 0; i < n; ++i)
        printf("%d, ", A[i]);
    
    printf("\n");
}

int main(int argc, char** argv)
{
    int size;
    int a[] = {2,2,0,0,2,0,2,1,0};
    size = sizeof(a)/sizeof(int);

    PrintArray(a, size);
    //SortColors(a, size);
    ColorSort(a, size);
    PrintArray(a, size);

    int b[] = {0,0,2,1,1,2,1,1,1,0,2,1,0,1,2,1,0,1,1,1,2,2,1,2,0,0,1,0,2,1,2,2,2,0};
    size = sizeof(b)/sizeof(int);

    PrintArray(b, size);
    //SortColors(b, size);
    ColorSort(b, size);
    PrintArray(b, size);
    
	/*
	 2, 2, 0, 0, 2, 0, 2, 1, 0, 
	 0, 0, 0, 0, 1, 2, 2, 2, 2, 
	 0, 0, 2, 1, 1, 2, 1, 1, 1, 0, 2, 1, 0, 1, 2, 1, 0, 1, 1, 1, 2, 2, 1, 2, 0, 0, 1, 0, 2, 1, 2, 2, 2, 0, 
	 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 
	 */
	
    return 0;
}