Sort An Array with Three Distinct Numbers (Microsoft Interview Question)

1. Problem Description

This is a Microsoft interview question for software develop engineer from careercup. Here is the orignal thread,

"

Sort an array of 0s, 1s and 2s 

Given an array A[] consisting 0s, 1s and 2s, write a function that sorts A[]. The functions should put all 0s first, then all 1s and all 2s in last.

Example
Input = {0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1};
Output = {0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2}

The problem is similar to http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Flag/

But they have added 1 trick into the question, You cannot use high = n;

It means don't calculate the length of array.

Can anyone help me in writing the code for this problem ?

- NoMind 10 days ago in India | Report Duplicate | Flag ".

2. Pseudo-code

The first idea popping into my head is to use the idea of quick sort. Use the mid value as the pivotal value to partition the array. But this will requires two traverse of the array. For instance,

    - pivotal value = 1, {2, 2, 2, 0, 0, 0, 1, 1, 1}

    - The first iteration: {1, 1, 1, 0, 0, 0, 2, 2, 2}

    - Then pick pivotal value = 0, on the left part {1, 1, 1, 0, 0, 0}

This process quires two traverses of the array. But the interviewers require only traversing the array only once.

My idea is to use the mid value as the pivotal value and start two partitions process as Example 1,

    - Partition 1: move the high value to the right

    - Partition 2: move the low value to the left

    - Start these two partitions process in the same traversing. 

Example 1

3. Implementation

// ********************************************************************************

// Implementation

// ********************************************************************************

#include <vector>

void SortArrayWith3DistinctNumbers(std::vector<int>& arr,

                                   const int low,

                                   const int mid,

                                   const int high)

{

    if (arr.empty()) {

        return;

    }

    const size_t len = arr.size();

    long posToHoldHigh = len - 1;

    while (posToHoldHigh >= 0 && arr[posToHoldHigh] == high) {

        --posToHoldHigh;

    }

    long posOfFirstOne = -1;

    for (long idx = 0; idx <= posToHoldHigh; ++idx) {

        if (arr[idx] == high) {

            // partition 1: move high (2) to the right

            arr[idx] = arr[posToHoldHigh];

            arr[posToHoldHigh] = high;

            while (posToHoldHigh >= 0 && arr[posToHoldHigh] == high) {

                --posToHoldHigh;

            }

        }

        if (arr[idx] == mid && posOfFirstOne < 0) {

            posOfFirstOne = idx;

        }

        if (arr[idx] == low && posOfFirstOne >= 0) {

            // partition 2: move low (0) to the left

            arr[idx] = mid;

            arr[posOfFirstOne] = low;

            ++posOfFirstOne;

        }

    }

}

// ********************************************************************************

// Test

// ********************************************************************************

#include <cassert>

void TestSortArrayWithThreeDistinctNumbers()

{

    std::vector<int> arr;

    SortArrayWith3DistinctNumbers(arr, 0, 1, 2);

    assert(arr.empty() == true);

    arr = { 2, 2, 2, 0, 0, 0, 1, 1, 1 };

    SortArrayWith3DistinctNumbers(arr, 0 , 1, 2);

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

    arr = { 0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1 };

    SortArrayWith3DistinctNumbers(arr, 0, 1, 2);

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

}