sundeepblue
4/15/2014 - 7:37 PM

given an array of size N whose contents are either 0, 1 or 2 (repeated, of course). Sort the array in a single pass.

given an array of size N whose contents are either 0, 1 or 2 (repeated, of course). Sort the array in a single pass.

sort_array_containing_0_1_2_only.cpp
content_copyfile_download
void sort_array_containing_0_1_2_only(vector<int> &A) {
    if(A.empty()) return;
    int i = 0, j = A.size()-1;
    int k = 0;
    while(k <= j) {   // gist, should <= j
        if(A[k] == 1) k++;
        else if(A[k] == 0) 
            swap(A[i++], A[k++]); // cannot forget to update k!!!
        else // A[k] == 2
            swap(A[j--], A[k]); // no ++?
    }
}

void sort_array_containing_012(vector<int>& A) {
    if(A.empty()) return;
    int edge_of_0 = 0;
    int edge_of_2 = A.size() - 1;
    int i = 0;
    while(edge_of_0 <= edge_of_2) {
        if(A[i] == 1)
            i++;
        else if(A[i] == 0)
            swap(A[edge_of_0++], A[i++]);
        else swap(A[edge_of_2--], A[i]); // no ++?
    }
}