Is there a specialized algorithm, faster than quic

问题:

I have some data coming from the hardware. Data comes in blocks of 32 bytes, and there are potentially millions of blocks. Data blocks are scattered in two halves the following way (a letter is one block):

A C E G I K M O B D F H J L N P

or if numbered

0 2 4 6 8 10 12 14 1 3 5 7 9 11 13 15

First all blocks with even indexes, then the odd blocks. Is there a specialized algorithm to reorder the data correctly (alphabetical order)?

The constraints are mainly on space. I don't want to allocate another buffer to reorder: just one more block. But I'd also like to keep the number of moves low: a simple quicksort would be O(NlogN). Is there a faster solution in O(N) for this special reordering case?

回答1:

Since this data is always in the same order, sorting in the classical sense is not needed at all. You do not need any comparisons, since you already know in advance which of two given data points.

Instead you can produce the permutation on the data directly. If you transform this into cyclic form, this will tell you exactly which swaps to do, to transform the permuted data into ordered data.

Here is an example for your data:

0 2 4 6 8 10 12 14 1 3  5  7  9 11 13 15
0 1 2 3 4 5  6  7  8 9 10 11 12 13 14 15

Now calculate the inverse (I'll skip this step, because I am lazy here, assume instead the permutation I have given above actually is the inverse already).

Here is the cyclic form:

(0)(1 8 4 2)(3 9 12 6)(5 10)(7 11 13 14)(15)

So if you want to reorder a sequence structured like this, you would do

# first cycle
# nothing to do

# second cycle
swap 1 8
swap 8 4
swap 4 2

# third cycle
swap 3 9
swap 9 12
swap 12 6

# so on for the other cycles

If you would have done this for the inverse instead of the original permutation, you would get the correct sequence with a proven minimal number of swaps.

EDIT:

For more details on something like this, see the chapter on Permutations in TAOCP for example.

回答2:

So you have data coming in in a pattern like

a₀ a₂ a₄...a₁₄ a₁ a₃ a₅...a₁₅

and you want to have it sorted to

b₀ b₁ b₂...b₁₅

With some reordering the permutation can be written like:

a₀ -> b₀

a₈ -> b₁
a₁ -> b₂
a₂ -> b₄
a₄ -> b₈

a₉ -> b₃
a₃ -> b₆
a₆ -> b₁₂
a₁₂ -> b₉

a₁₀ -> b₅
a₅ -> b₁₀

a₁₁ -> b₇
a₇ -> b₁₄
a₁₄ -> b₁₃
a₁₃ -> b₁₁

a₁₅ -> b₁₅

So if you want to sort in place it with only one block additional space in a temporary t, this could be done in O(1) with

t = a8;   a8 = a4;  a4 = a2;  a2 = a1;  a1 = t

t = a9;   a9 = a12; a12= a6;  a6 = a3;  a9 = t

t = a10; a10 = a5;  a5 = t

t = a11; a11 = a13; a13 = a14; a14 = a7; a7 = t

Edit:
The general case (for N != 16), if it is solvable in O(N), is actually an interesting question. I suspect the cycles always start with a prime number which satisfies p < N/2 && N mod p != 0 and the indices have a recurrence like i_n+1 = 2i_n mod N, but I am not able to prove it. If this is the case, deriving an O(N) algorithm is trivial.

回答3:

maybe i'm misunderstanding, but if the order is always identical to the one given then you can "pre-program" (ie avoiding all comparisons) the optimum solution (which is going to be the one that has the minimmum number of swaps to move from the string given to ABCDEFGHIJKLMNOP and which, for something this small, you can work out by hand - see LiKao's answer).

回答4:

It is easier for me to label your set with numbers:

0 2 4 6 8 10 12 14 1 3 5 7 9 11 13 15

Start from the 14 and move all even numbers to place (8 swaps). You will get this:

0 1 2 9 4 6 13 8 3 10 7 12 11 14 15

Now you need another 3 swaps (9 with 3, 7 with 13, 11 with 13 moved from 7).

A total of 11 swaps. Not a general solution, but it could give you some hints.

回答5:

You can also view the intended permutation as a shuffle of the address-bits `abcd <-> dabc' (with abcd the individual bits of the index) Like:

#include <stdio.h>

#define ROTATE(v,n,i) (((v)>>(i)) | (((v) & ((1u <<(i))-1)) << ((n)-(i))))

/******************************************************/
int main (int argc, char **argv)
{
unsigned i,a,b;

for (i=0; i < 16; i++) {
        a = ROTATE(i,4,1);
        b = ROTATE(a,4,3);

        fprintf(stdout,"i=%u a=%u b=%u\n", i, a, b);
        }

return 0;
}

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

回答6:

That was count sort I believe