Radix-Sort für Negative Ganzzahlen

Bin ich versucht zu implementieren radix-sort für Ganzzahlen einschließlich negative zahlen. Für nicht-negative int-Werte, die ich planen, zu erstellen Sie eine Warteschlange von 10 queues entsprechend für die Ziffern 0-9 und die Umsetzung der LSD-Algorithmus. Aber ich war irgendwie verwirrt mit den negativen ganzen zahlen. Was ich jetzt denke, ist, gehen Sie voran und erstellen Sie eine andere Warteschlange von 10 queues für Sie und separat sortiert und dann, am Ende, ich gab 2 Listen, eine mit negativen int-Werten sortiert und die anderen, die nicht-negative Ganzzahlen. Und schließlich würde ich Sie Zusammenführen.

Was haltet Ihr von diesem? Ist es effizienter Umgang mit negativen ganzen zahlen?

Danke!

InformationsquelleAutor gtkesh | 2013-03-09

27

Können Sie behandeln das Zeichen als eine Besondere Art von Stelle. Sie Sortieren die Stapel auf die Einheiten, dann die Zehner, etc. und schließlich auf dem Schild. Dies erzeugt eine umgekehrte Reihenfolge für die negative, du dann einfach rückwärts den Inhalt der Eimer. Es ist so alt wie die mechanische Karten-Sortierer gearbeitet.
- Das macht mehr Sinn. Danke!!!
- Vielen Dank für das teilen, wie die alte mechanische Karten-Sortierer gearbeitet!
- Dies erfordert einen pass mehr als notwendig. Spiegeln nur das Vorzeichen-bit vor der Sortierung.
InformationsquelleAutor Peter Wooster
5

Beachten Sie, dass das Vorzeichen-bit wird das oberste bit in einer signed integer, aber alle zahlen behandelt werden, die von radix-sort als unsigned Integer standardmäßig. Sie müssen also sagen, der Algorithmus, der die negativen zahlen sind kleiner als die positiven. Im Fall von 32-bit-Ganzzahlen mit Vorzeichen, können Sie eine Sortierreihenfolge für drei unteren Byte zuerst, dann Sortieren Sie die vierte (Obere) byte mit dem Vorzeichen-bit invertiert, so dass 0 wird für negative zahlen verwendet anstelle von 1, und folglich werden Sie als erste gehen.

Empfehle ich dringend zum Sortieren von zahlen (byte-by-byte anstelle von Dezimalstellen, denn es ist viel leichter für die Maschine zu Holen bytes als Auszug stellen.
- Anstelle der Invertierung der Vorzeichen-bit, Sie können auch kombinieren Sie einfach die Eimer in einer anderen Reihenfolge. Wenn Sie mit 16 Eimern, Beginnen Sie mit Eimer 8 - 15 und dann gehen Sie zurück und tun, 0 - 7, und dies wird produzieren die gleiche Bestellung.
InformationsquelleAutor punpcklbw
3

Eine weitere Lösung ist die Trennung von negativen ganzen zahlen von der Reihe, machen Sie positive, Art als positive Werte mit radix, dann drehen Sie es und fügen Sie mit sortierten nicht-negative array.
- Akzeptieren Sie Ihre eigene Antwort nach unaccepting jemand anderes, dass tatsächlich gab Ihnen die Lösung, die ist ziemlich unhöflich.
- +1 auf die Frage zum Verhängnis geworden, dass!
InformationsquelleAutor gtkesh

Absolut! Man muss natürlich aufpassen, dass Sie von der Aufteilung des negativen vom positiven, aber zum Glück ist dies ganz einfach. Am Anfang des Algorithmus Sortieren alles, was Sie tun müssen, ist Ihre partition-array um den Wert 0. Danach radix-Sortierung unter-und oberhalb der Trennwand.

Hier ist der Algorithmus in der Praxis. Ich abgeleitet, das von Kevin Wayne und Bob Sedgewick ist 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;
}

InformationsquelleAutor AtlasMeh-ed

Wohl die einfachste Art das zu handhaben, signierte Werte für den Versatz der Startposition für die Akkumulation (d.h., die Generierung von positions-offsets) bei Betrieb an den meisten signifikante Ziffer. Die Umwandlung der Eingabe, so werden alle Ziffern behandelt werden dürfen als unsigned ist auch eine option, erfordert aber die Anwendung eines Vorgangs über die array Werte mindestens zweimal (einmal, um vorzubereiten, die Eingang und um wieder die Ausgabe).

Diese nutzt die erste Technik sowie byte-Größe stellen (byte-Zugriff ist in der Regel effizienter):

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

Hinweis: Code ist ungetestet. Entschuldigungen für Fehler/Tippfehler.

InformationsquelleAutor John Q.

1

Ihrem radix-sort nicht schneller sein als der berühmte Vergleich von Sorten, wenn Sie nicht verwenden "bitshift" und "bitweise UND" für radix Berechnung.

Computer verwenden 2 ergänzen zu vertreten, unterzeichnet zahlen, hier das sign-bit liegt am äußersten linken Ende eine binäre Ziffer, die in dem Hauptspeicher

eg

436163157 (als 32 bit-Zahl) = 00011001 11111111 01010010 01010101
-436163157 (als 32 bit-Zahl) = 11100110 00000000 10101101 10101011

1 (als 32 bit-Zahl) = 00000000 00000000 00000000 00000001

-1 (als 32 bit-Zahl) = 11111111 1111111 1111111 11111111

0 wird dargestellt als = 00000000 00000000 00000000 00000000

Höchsten negativen Wert as = 10000000 00000000 00000000 00000000

Damit Sie sehen, desto mehr negative einer Zahl wird, verliert es, dass viele 1, eine kleine negative Zahl hat viele 1, wenn Sie nur das Vorzeichen-bit 0 ist, wird es eine sehr große positive Zahl ist. Umgekehrt ist eine kleine positive Zahl ist, wird eine große negative Zahl.

Im radix sort die Schlüssel zu Sortieren negativen zahlen ist, wie Sie behandeln die letzten 8 bit für negative zahlen mindestens das Letzte bit muss 1 sein, in 32-bit-System, es hat aus
10000000 00000000 00000000 00000000 die die meisten negativen Wert, der am weitesten von null auf 11111111 11111111 11111111 11111111, das ist -1. Wenn man sich die linken 8 bits, die Größenordnung reicht von 10000000 bis 11111111, also von 128 bis 255.

Diese Werte können erhalten werden, indem dieser code Stück
```
V = ( A[i] >> 24 ) & 255
```
Für negative zahlen V wird immer die Lüge von 128 bis 255. Für positive zahlen, es wird von 0 bis 127. Wie bereits gesagt, der Wert von M wird 255 -1 und 128 für höchste negative Zahl in 32-bit-System. Bauen Sie sich Ihr Histogramm als üblich. Dann ab index 128 bis 255 zu tun, die kumulative Summe, dann fügen Sie die Frequenz von 255 auf 0 aus, und fahren Sie die kumulative Summe von 0 bis index 127. Führen Sie die Art, wie üblich. Diese Technik ist sowohl eine optimale, schnelle, elegante und gepflegte sowohl in der Theorie und in der Praxis. Keine Notwendigkeit, jede Art von separaten Listen noch, um die Umkehr nach der Sortierung noch die Konvertierung aller Eingänge zu positiven, welche die Art langsam und chaotisch.

Für den code sehen Radix-Sort Optimierung
64-bit-version gebaut werden kann, mit der gleichen Konzepte

Weiter Lesen:

http://codercorner.com/RadixSortRevisited.htm

http://stereopsis.com/radix.html

InformationsquelleAutor ytoamn

Diese kann getan werden, ohne Partitionierung oder dass praktisch invertieren des MSB. Hier ist eine funktionierende Lösung in 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;
    }
}

InformationsquelleAutor Abhijit Sarkar

0

Akzeptiert die Antwort erfordert einen pass mehr als notwendig.

Spiegeln nur das Vorzeichen-bit.

Dies ist im wesentlichen die Antwort gepostet von punpcklbw, aber es gibt eine kleine Einschränkung, die behandelt werden muss. Konkret wird angenommen, Sie arbeiten mit einem zweier-Komplement-Darstellung, die wahr ist für 99,999% der uns. Zum Beispiel, Java und Rost festlegen, dass signierte ganze zahlen verwenden zweier-Komplement. Die C-und C++ - Spezifikationen erfordern keine spezifischen format, aber weder MSVC, GCC, noch LLVM support sonstigen Darstellungen. In der Montage, In fast jedem CPU-beschäftigen Sie sich mit zweier-Komplement, und Sie werden sicherlich schon wissen, sonst.

Die folgende Tabelle zeigt, dass die spiegelung einfach das Vorzeichen-bit wird dazu führen, dass zwei-Komplement-Ganzzahlen zu Sortieren richtig, wenn Sie lexikographisch sortiert. Die erste Spalte gibt einen binary-Wert, die zweite Spalte gibt die interpretation der bits als 4-bit-Ganzzahlen mit Vorzeichen, und die Dritte Spalte gibt die interpretation der bits mit dem hohen bit umgedreht.
```
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
```
Die Antwort punpcklbw empfiehlt spiegeln nur das bit, wenn Sie das höchste byte, aber mein Bauchgefühl sagt mir, es wäre schneller, einfach flip das oberste bit jedes mal, bevor Sie ziehen Sie das byte, die Sie suchen. Das ist, weil dabei ein einziges xor-jeder Zeit spiegeln, die etwas schneller sein wird als ein Zweig jedes mal zu entscheiden, ob flip oder nicht.

[Ein wichtiges detail zu erwähnen, die einige Lehrbücher nicht richtig ist, dass eine wirkliche Umsetzung sollte die Sortierung nach byte, nicht durch die dezimale Ziffer. Dies ist natürlich immer noch korrekt, weil Sie nur die Sortierung durch eine Wurzel von 256 statt 10, aber denken Sie an es auf diese Weise führt zu einer besseren Implementierungen.]

InformationsquelleAutor cbarrick

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.