What is the best stable sorting algorithm when my keyspace contains only two elements

Question

The alphabet contains only two numbers, for example

[0, 0, 1, 1, 0, 1, 0, 1] 

and it can be really big (at least millions) I need to soften it with swap operations (when I swap, I will also make the same changes in adjacent data structures). Sorting must also be stable.

In my case, the swap operation is expensive, the sorting algorithm should also minimize them.

O (n) additional spatial complexity is acceptable if the number of swaps is significantly reduced.

What is the best sorting algorithm in this case?

Answer 1

0/1 - int [], :

• 0s 1s . ;

• , ;

• , 0/1 0 1 . , , 1, 0, 1s

:

void zeroOneSort<T>(int *keys, T *values, int len)
{
    //count zeros
    int numZeros = 0;
    for(int i=0; i<len; ++i)
    {
        if (!keys[i])
           ++numZeros;
    }

    //fill in positions
    {
        int zeroPos=0, onePos = numZeros;
        for(int i=0; i<len; ++i)
        {
            if (!keys[i])
               keys[i] = zeroPos++;
            else
               keys[i] = onePos++;
        }
    }

    //swap into place
    for(int i=0; i<len; ++i)
    {
        int target;
        while ((target=keys[i])!=i)
        {
           std::swap(keys[i],keys[target]);
           std::swap(values[i],values[target]);
        }
    }

    //fix up keys
    for(int i=0; i<numZeros; ++i)
    {
        keys[i]=0;
    }
    for(int i=numZeros; i<len; ++i)
    {
        keys[i]=1;
    }
}

, N-1 , ( , ), .

- , , .