Tri Radix pour les entiers négatifs

notez que le bit de signe est le bit le plus haut dans un entier signé, mais tous les nombres sont traités par le tri radix comme des entiers non signés par défaut. Donc vous devez dire à l'algorithme que les nombres négatifs sont plus petits que les nombres positifs. Dans le cas des entiers signés 32 bits, vous pouvez d'abord trier trois octets inférieurs, puis trier le quatrième (octet supérieur) avec le bit de signe inversé de sorte que 0 sera utilisé pour les nombres négatifs au lieu de 1, et par conséquent ils iront en premier.

je vous conseillez de trier les nombres byte-Byte plutôt que par des chiffres décimaux, parce qu'il est beaucoup plus facile pour la machine de ramasser des bytes que d'extraire des chiffres.

une solution de plus est de séparer les entiers négatifs du tableau, de les rendre positifs, de les trier comme des valeurs positives en utilisant radix, puis de les inverser et de les ajouter avec le tableau non-négatif trié.

Absolument! Bien sûr, vous ne devez prendre soin de diviser les aspects négatifs de l'positifs, mais heureusement, c'est facile. Au début de votre algorithme de tri tout ce que vous avez à faire est la partition de votre tableau autour de la valeur 0. Après cela, radix trier ci-dessous et au-dessus de la partition.

Voici l'algorithme en pratique. J'ai tiré cette de Kevin Wayne et Bob Sedgewick du MSD radix sort: 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;
}

probablement la façon la plus facile de gérer les valeurs signées est de décaler la position de départ pour l'accumulation (c.-à-d. la génération de décalages de position) quand on opère sur le chiffre le plus significatif. Transformer l'entrée de manière à ce que tous les chiffres puissent être traités comme non signés est également une option, mais nécessite d'appliquer une opération sur le tableau des valeurs au moins deux fois (une fois pour préparer l'entrée et une autre pour restaurer la sortie).

ceci utilise la première technique aussi bien que octets de taille chiffres (octets accès est généralement plus efficace):

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);
    }
}

Remarque: le Code n'est pas testé. Excuses pour les erreurs/fautes de frappe.

votre type radix ne sera pas plus rapide que les célèbres types de comparaison si vous n'utilisez pas "bitshift" et "bitwise AND" pour le calcul de radix.

les ordinateurs utilisent le complément 2 pour représenter les nombres signés, ici le signe-bit se trouve à l'extrémité gauche d'un chiffre binaire, dans la représentation de mémoire

par exemple

436163157 (32 bits) = 0 0011001 11111111 01010010 01010101

-436163157 (32 bits) = 1 1100110 00000000 10101101 10101011

1 (32 bits) = 00000000 00000000 00000000 00000001

-1 (32 bits) = 1 1111111 1111111 1111111 111111

0 est représenté par = 00000000 00000000 00000000 00000000

La plus haute valeur négative = 10000000 00000000 00000000 00000000

ainsi, vous voyez, plus un nombre devient négatif, il perd beaucoup de 1, Un petit le nombre négatif a beaucoup de 1, si vous mettez seulement le signe-bit à 0, Il devient un nombre positif très grand. Inversement, un petit nombre positif devient un grand nombre négatif.

dans le tri radix la clé pour trier les nombres négatifs est comment vous gérez les 8 derniers bits, pour les nombres négatifs au moins le dernier bit doit être 1, dans le schéma 32 bits il doit être de

10000000 00000000 00000000 00000000 qui est la valeur la plus négative la plus éloignée de zéro à 11111111 11111111 111111 111111 qui est -1. Si vous regardez les 8 bits les plus à gauche, la magnitude varie de 10000000 à 11111111, c'est-à-dire de 128 à 255.

Ces valeurs peuvent être obtenues par ce morceau de code

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

pour les nombres négatifs, V se situera toujours entre 128 et 255. Pour les nombres positifs, il sera de 0 à 127. Comme indiqué précédemment, la valeur de M sera de 255 pour -1 et 128 pour le nombre négatif le plus élevé dans le schéma de 32 bits. Construire votre histogramme comme à l'habitude. Ensuite, de l'index 128 à l'index 255 font la somme cumulative, puis ajoutent la fréquence de 255 à 0, et procèdent à la somme cumulative de 0 jusqu'à l'index 127. Effectuer le Tri, comme d'habitude. Cette technique est à la fois optimale, rapide, élégante et soignée en théorie et en pratique. Pas besoin de listes séparées, ni d'inversion d'ordre après tri, ni de conversion de toutes les entrées en entrées positives qui rendent le tri lent et désordonné.

pour le code voir Optimisation De Tri Radix

Un La version 64 bits peut être construite avec les mêmes concepts



Plus read:

http://codercorner.com/RadixSortRevisited.htm

http://stereopsis.com/radix.html

ceci peut être fait sans avoir besoin de partitionner ou d'Inverser pratiquement L'ESM. Voici une solution de travail en Java:

public class RadixSortsInterviewQuestions {
    private static final int MSB = 64;

    static Map.Entry<Integer, Integer> twoSum(long[] a, long sum) {
        int n = a.length - 1;
        sort(a, MSB, 0, n);

        for (int i = 0, j = n; i < j; ) {
            long t = a[i] + a[j];
            if (t == sum) {
                return new SimpleImmutableEntry<>(i, j);
            } else if (t < sum) {
                i++;
            } else {
                j--;
            }
        }
        return null;
    }

    // Binary MSD radix sort: https://en.wikipedia.org/wiki/Radix_sort#In-place_MSD_radix_sort_implementations
    private static void sort(long[] a, int d, int lo, int hi) {
        if (hi < lo || d < 1) return;

        int left = lo - 1;
        int right = hi + 1;

        for (int i = left + 1; i < right; ) {
            if (isBitSet(a[i], d)) {
                swap(a, i, --right);
            } else {
                left++;
                i++;
            }
        }
        sort(a, d - 1, lo, left);
        sort(a, d - 1, right, hi);
    }

    private static boolean isBitSet(long x, int k) {
        boolean set = (x & 1L << (k - 1)) != 0;

        // invert signed bit so that all positive integers come after negative ones
        return (k == MSB) != set;
    }

    private static void swap(long[] a, int i, int j) {
        long tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }
}

la réponse acceptée exige une réussite de plus que nécessaire.

il suffit de retourner le panneau bit.

c'est essentiellement la réponse Postée par punpcklbw, mais il y a une petite mise en garde qui doit être abordée. Plus précisément, cela suppose que vous travaillez avec un double complément de représentation, ce qui est vrai pour 99,999% d'entre nous. Par exemple, Java et Rust spécifient que les entiers signés utilisent le complément de two. Les spécifications C et c++ ne nécessitent pas de format, mais ni MSVC, GCC, ni LLVM soutenir d'autres représentations. En assemblée, presque n'importe quel CPU que vous allez traiter est le complément de deux, et vous le saurez sûrement déjà autrement.

le tableau suivant montre que le simple fait de retourner le bit de signe causera un tri correct des entiers de Two-complement lorsqu'ils sont triés lexicographiquement. La première colonne donne une valeur binaire, la deuxième colonne donne l'interprétation de ces bits 4 bits entiers signés, et la troisième colonne donne l'interprétation de ces morceaux avec la haute peu flippée.

Binary    | 2s-comp  | Flip sign
----------+----------+----------
0000      | 00       | -8
0001      | +1       | -7
0010      | +2       | -6
0011      | +3       | -5
0100      | +4       | -4
0101      | +5       | -3
0110      | +6       | -2
0111      | +7       | -1
1000      | -8       | 00
1001      | -7       | +1
1010      | -6       | +2
1011      | -5       | +3
1100      | -4       | +4
1101      | -3       | +5
1110      | -2       | +6
1111      | -1       | +7

la réponse donnée par punpcklbw ne recommande de retourner le morceau que lorsque vous regardez le plus haut octet, mais mon instinct me dit qu'il serait plus rapide de simplement retourner le morceau supérieur à chaque fois avant que vous tirez le octet que vous regardez. C'est parce que faire un XOR simple à chaque fois pour retourner le peu sera plus rapide que faire une branche à chaque fois pour décider si vous devriez retourner ou non.

[Un un détail important à mentionner, que certains manuels ne traitent pas correctement, est qu'une mise en œuvre réelle devrait Trier par octet, et non par décimal. C'est évidemment encore correct, parce que vous êtes juste en train de trier par un radix de 256 au lieu de 10, mais penser à ce sujet de cette façon conduira à de meilleures implémentations.]