Saturday, October 1, 2011

Sort array which contains only 0, 1 or 2 in O(n)


void Sort(int* arr, int length)
{
    for (int low = 0, mid = 0, high = length-1; mid<=high;)
    {
        switch(arr[mid])
        {
        case 0: Swap(arr[low++], arr[mid++]);
                break;
        case 1: ++mid;
                break;
        case 2: Swap(arr[mid], arr[high--]);
                break;
        }
    }
}

No comments:

Post a Comment