sorting - son - Ordenar radix para enteros negativos

radix sort c++ codigo

Question

Estoy tratando de implementar radix sort para enteros, incluidos los enteros negativos. Para ints no negativos, estaba planeando crear una cola de 10 colas correspondientemente para los dígitos 0-9 e implementar el algoritmo LSD. Pero estaba un poco confundido con enteros negativos. Lo que estoy pensando ahora, es seguir adelante y crear otra cola de 10 colas para ellos y clasificarlos por separado y luego, al final, daré 2 listas, una que contenga entradas negativas ordenadas y la otra que contenga entradas no negativas. Y finalmente los fusionaría.

¿Qué piensas sobre esto? ¿Hay una manera más eficiente de manejar con enteros negativos?

¡Gracias!

Answer 1

Su clasificación de radix no será más rápida que las clases de comparación famosas si no usa "bitshift" y "AND a nivel de bit" para el cálculo de radix.

Las computadoras usan el complemento 2 para representar números con signo, aquí el bit de signo se encuentra en el extremo izquierdo de un dígito binario, en representación de memoria

p.ej
436163157 (como número de 32 bits) = 0 0011001 11111111 01010010 01010101
-436163157 (como número de 32 bits) = 1 1100110 00000000 10101101 10101011

1 (como número de 32 bits) = 0 0000000 00000000 00000000 00000001
-1 (como número de 32 bits) = 1 1111111 1111111 1111111 11111111

0 se representa como = 0 0000000 00000000 00000000 00000000
El valor negativo más alto es = 1 0000000 00000000 00000000 00000000

Como ve, cuanto más negativo se vuelve un número, pierde muchos 1, un número negativo pequeño tiene muchos 1, si establece solo el bit de signo en 0, se convierte en un número positivo muy grande. A la inversa, un pequeño número positivo se convierte en un gran número negativo.

En la ordenación de radix, la clave para clasificar los números negativos es cómo manejar los últimos 8 bits, para los números negativos, al menos, el último bit debe ser 1, en el esquema de 32 bits que tiene que ser de
1 0000000 00000000 00000000 00000000 que es el valor más negativo más alejado de cero a 1 1111111 11111111 11111111 11111111 que es -1. Si miras los 8 bits más a la izquierda, la magnitud va de 10000000 a 11111111, es decir, de 128 a 255.

Estos valores se pueden obtener mediante esta pieza de código

V = ( A[i] >> 24 ) & 255

Para números negativos, V siempre estará entre 128 y 255. Para números positivos será de 0 a 127. Como se dijo anteriormente, el valor de M será 255 para -1 y 128 para el número negativo más alto en el esquema de 32 bits. Construya su histograma como de costumbre. Luego, desde el índice 128 a 255 haga la suma acumulativa, luego agregue la frecuencia de 255 a 0, y proceda con la suma acumulada desde 0 hasta el índice 127. Realice la clasificación como de costumbre. Esta técnica es óptima, rápida, elegante y ordenada tanto en teoría como en la práctica. No hay necesidad de ningún tipo de listas separadas ni de inversión de órdenes después de ordenar ni convertir todas las entradas en positivas, lo que hace que el orden sea lento y desordenado.

Para ver el código, vea Optimización de clasificación de radix
Una versión de 64 bits se puede construir utilizando los mismos conceptos

Lea más:
http://codercorner.com/RadixSortRevisited.htm
http://stereopsis.com/radix.html

Answer 2

Puede tratar el letrero como un tipo especial de dígito. Usted ordena la pila en las unidades, luego las decenas, etc. y finalmente en el letrero. Esto produce un orden inverso para los negativos, luego simplemente invierte el contenido de ese cubo. Es como funcionaban los viejos clasificadores mecánicos de tarjetas.

Answer 3

Una solución más es separar enteros negativos de la matriz, hacerlos positivos, ordenarlos como valores positivos usando radix, luego revertirlos y anexarlos con matriz ordenada no negativa.

Answer 4

¡Absolutamente! Por supuesto, tienes que encargarte de dividir los aspectos negativos de los positivos, pero afortunadamente esto es fácil. Al principio de su algoritmo de clasificación, todo lo que tiene que hacer es dividir su matriz en torno al valor 0. Después de eso, clasifique por debajo y debajo de la partición.

Aquí está el algoritmo en la práctica. Lo obtuve del tipo MSD radix de Kevin Wayne y Bob Sedgewick: http://algs4.cs.princeton.edu/51radix/MSD.java.html

private static final int CUTOFF = 15;
private static final int BITS_PER_INT = 32;
private static final int BITS_PER_BYTE = 8;
private static final int R = 256;

public void sort(int[] a){
    int firstPositiveIndex = partition(0, a, 0, a.length-1);
    int[] aux =new int[a.length];
    if(firstPositiveIndex>0){
        recSort(a, firstPositiveIndex, a.length-1, 0,aux);
        recSort(a, 0, firstPositiveIndex-1, 0,aux);
    }else{//all positive
        recSort(a, 0, a.length-1, 0, aux);
    }
}

private void recSort(int[] a, int lo, int hi, int d, int[] aux){
    if(d>4)return;
    if(hi-lo<CUTOFF){
        insertionSort(a,lo, hi);
        return;
    }

    int[] count = new int[R+1];

    //compute counts
    int bitsToShift = BITS_PER_INT-BITS_PER_BYTE*d-BITS_PER_BYTE;
    int mask = 0b1111_1111;
    for(int i = lo; i<=hi; i++){
        int c = (a[i]>>bitsToShift) & mask;
        count[c+1]++;
    }

    //compute indices
    for(int i = 0; i<R; i++){
        count[i+1]=count[i]+count[i+1];
    }

    //distribute
    for(int i = lo; i<=hi; i++){
        int c = (a[i]>>bitsToShift) & mask;
        aux[count[c]+lo] = a[i];
        count[c]++;
    }
    //copy back
    for(int i = lo; i<=hi; i++){
        a[i]=aux[i];
    }

    if(count[0]>0)
        recSort(a, lo, lo+count[0]-1, d+1, aux);
    for(int i = 1; i<R; i++){
        if(count[i]>0)
            recSort(a, lo+count[i-1], lo+count[i]-1, d+1, aux);
    }
}

// insertion sort a[lo..hi], starting at dth character
private void insertionSort(int[] a, int lo, int hi) {
    for (int i = lo; i <= hi; i++)
        for (int j = i; j > lo && a[j] < a[j-1]; j--)
            swap(a, j, j-1);
}


//returns the index of the partition or to the right of where it should be if the pivot is not in the array 
public int partition(int pivot, int[] a, int lo, int hi){
    int curLo = lo;
    int curHi = hi;
    while(curLo<curHi){
        while(a[curLo]<pivot){
            if((curLo+1)>hi)return hi+1;
            curLo++;
        }

        while(a[curHi]>pivot){
            if((curHi-1)<lo)return lo-1;
            curHi--;
        }
        if(curLo<curHi){
            swap(a, curLo, curHi);
            if(a[curLo]!=pivot)curLo++;
            if(a[curHi]!=pivot)curHi--;             
        }
    }
    return curLo;
}


private void swap(int[] a, int i1, int i2){
    int t = a[i1];
    a[i1]=a[i2];
    a[i2]=t;
}

Answer 5

Tenga en cuenta que el bit de signo es el bit más superior en un entero con signo, pero todos los números se tratan por orden de radix como enteros sin signo de forma predeterminada. Entonces, necesitas decirle al algoritmo que los números negativos son más pequeños que los positivos. En el caso de enteros con signo de 32 bits, primero puede ordenar tres bytes inferiores, luego ordenar el cuarto byte (superior) con el bit de signo invertido para que 0 se use para números negativos en lugar de 1, y en consecuencia irán primero.

Recomiendo encarecidamente clasificar números byte por byte en lugar de dígitos decimales, porque es mucho más fácil para la máquina recoger bytes que extraer dígitos.

Answer 6

Probablemente la forma más fácil de manejar los valores firmados es compensar la posición de inicio de la acumulación (es decir, la generación de desplazamientos posicionales) cuando se opera en el dígito más significativo. Transformar la entrada para que todos los dígitos puedan tratarse como sin signo también es una opción, pero requiere aplicar una operación sobre la matriz de valores al menos dos veces (una para preparar la entrada y otra para restaurar la salida).

Utiliza la primera técnica así como los dígitos del tamaño de un byte (el acceso por bytes generalmente es más eficiente):

void lsdradixsort(int* a, size_t n)
{
    // isolate integer byte by index.
    auto bmask = [](int x, size_t i)
    {
        return (static_cast<unsigned int>(x) >> i*8) & 0xFF;
    };

    // allocate temporary buffer.
    auto m = std::make_unique<int[]>(n);
    int* b = m.get();

    // for each byte in integer (assuming 4-byte int).
    for ( size_t i, j = 0; j < 4; j++ ) {
        // initialize counter to zero;
        size_t h[256] = {}, start;

        // histogram.
        // count each occurrence of indexed-byte value.
        for ( i = 0; i < n; i++ )
            h[bmask(a[i], j)]++;

        // accumulate.
        // generate positional offsets. adjust starting point
        // if most significant digit.
        start = (j != 3) ? 0 : 128;
        for ( i = 1+start; i < 256+start; i++ )
            h[i % 256] += h[(i-1) % 256];

        // distribute.
        // stable reordering of elements. backward to avoid shifting
        // the counter array.
        for ( i = n; i > 0; i-- )
            b[--h[bmask(a[i-1], j)]] = a[i-1];
        std::swap(a, b);
    }
}

Nota: El código no está probado. Disculpas por cualquier error / error tipográfico.