[Resolvido] Dúvida Radix Sort

[lesiano16]

Boas, estava analisar o código do radix sort e estou com algumas dúvidas a perceber uma parte dele.

#define swap(a, b) { tmp = a; a = b; b = tmp; }

/* sort unsigned ints */
static void rad_sort_u(unsigned *from, unsigned *to, unsigned bit)
{
if (!bit || to < from + 1) return;

unsigned *ll = from, *rr = to - 1,tmp;
while (1) {
	/* find left most with bit, and right most without bit, swap */
	while (ll < rr && !(*ll & bit)) ll++;
	while (ll < rr &&  (*rr & bit)) rr--;
	if (ll >= rr) break;
	swap(*ll, *rr);
}

if (!(bit & *ll) && ll < to) ll++;
bit >>= 1;

rad_sort_u(from, ll, bit);
rad_sort_u(ll, to, bit);
}

/* sort signed ints: flip highest bit, sort as unsigned, flip back */
static void radix_sort(int *a, const size_t len)
{
size_t i;
unsigned *x = (unsigned*) a;

for (i = 0; i < len; i++)
           x[i] ^= INT_MIN;

rad_sort_u(x, x + len, INT_MIN);

for (i = 0; i < len; i++)
           x[i] ^= INT_MIN;
}

Não percebo o porque desta linha de código:

for (i = 0; i < len; i++)  x[i] ^= INT_MIN;

Se alguém me pudesse dar uma luz agradecia.

[KTachyon]

^ é um XOR (exclusive OR). http://en.wikipedia.org/wiki/Exclusive_or

x[i] = x[i] ^ INT_MIN;

[lesiano16]

Certissimo. O que eu não percebo é a utilidade da sua utilização no contexto deste algoritmo.

[KTachyon]

Assumindo que o INT_MIN é o valor mínimo que podes ter num signed int, e olhando para o comentário que está por cima do código dessa função, eu diria que serve para trocar o bit de sinal, caso este seja negativo.

Imaginando um número em 4 bits,

0111 =  7

1000 = -8

1001 = -7

1010 = -6

1011 = -5

1100 = -4

1101 = -3

1110 = -2

1111 = -1

0000 =  0

O que a instrução faz é (para -6):

1010 ^ 1000 = 0010 (em unsigned: 10 -> 2)

Para 6:

0110 ^ 1000 = 1110 (em unsigned: 6 -> 16)

Como depois vais ordenar como unsigned (sem sinal), os valores que eram positivos vão continuar maiores que os negativos mas representados como unsigned.

Depois, quando voltas para o método, voltas a colocar o sinal da mesma forma como os trocaste 🙂

[lesiano16]

Desculpa la fazer perder o teu tempo, mas já percebi a cena é que quando mandava imprimir para ver o que estava a fazer estava a representa-lo com inteiro, e como tal aparecia negativos e positivos mas devia imprimir com %u em vez de %d.

Obrigadão pela ajuda.

[KTachyon]

Já estava a responder, mas, ya, é isso 😉