Sortieralgorithmus

[Heinrich500]

Hallo,
ich will Integer sortieren. Dabei kann ich diese als 32 Zeichen lange Folge von 0 und 1 auffassen und diese mit dem verallgemeinerten Bucketsortverfahren sortieren.
Dabei ist bis jetzt folgendes herausgekommen:

public static void sort(List<Integer> numbers) {
      
      
        Queue<Integer> tmp =new LinkedList<Integer>();
         for (int i = 0; i < numbers.size(); i++) {
             tmp.offer(numbers.get(i));
         }
      
      
        List<Integer>[] bucket = new ArrayList[2];
        for(int i=0; i<bucket.length; i++) {
            bucket[i] = new ArrayList<Integer>();
            }
  
        for(int k=32; k>0;k--) {
             //clear
            for(int i=0;i<bucket.length;i++) {
                bucket[i].clear();
            }
      
            while(!tmp.isEmpty()) {
                Integer oberstesEl =tmp.element();
                String el =String.valueOf(oberstesEl);
                if(el.charAt(k-1)==0) {
                    bucket[0].add(oberstesEl);
                }
                else {
                    bucket[1].add(oberstesEl);
                }
                tmp.remove();
          
            }
          
            for(int i=0; i<bucket.length;i++) {
                for (Integer j : bucket[i]) {
                      tmp.add(j);
                }
            }
  
        }
    }

Was sagt ihr dazu. Ich weis nicht ganz, wie ich das mit Binärzahlen testen kann. Aber würde es so funktionieren?

 

[mihe7]

ich will Integer sortieren. Dabei kann ich diese als 32 Zeichen lange Folge von 0 und 1 auffassen und diese mit dem verallgemeinerten Bucketsortverfahren sortieren.

Ich versteh nur Bahnhof.

 

[Heinrich500]

Es geht egtl um die Anwendung des Algorithmus für das Sortieren von Strings fester Länge. Es handelt sich gewissermaßen um eine Veralllgemeinerung von Bucketsort.
Es soll auf der Grundlage dieses Algorithmus nicht negative ganze Zahlen sortiert werden, Diese können als Strings der Länge 32 auf dem Alphabet {0,1} betrachetet werden. Kann man das besser verstehen?
Was hältst du von meinem Algo?

 

[Xyz1]

Ich versteh nur Bahnhof.

@mihe7 :

... er meint wahrscheinlich Countingsort.

 

[Heinrich500]

Ja eine Veralllgemeinerung von Bucketsort. Man legt eine Queue von Strings an, die jeweils die gleichen Längen haben, und betrachtet dann jeweils jede der 32 Komponenten der einzelen Strings von hinten nach vorne. Auf jede Komponente wendet man Bucketsort mit den beiden Buckets 0 und 1 an. Man nimmt als solange die Queue nicht leer ist, die Strings her, schaut ob an der i-ten Stelle eine 0 oder 1 steht und fügt dann den String in den jeweiligen Bucket. Dann konkateniert die Elemente der buckets wieder zu einer Queue usw. Dabei nutzt man , dass Bucketsort stabil ist.

 

[mihe7]

Nur macht Dein Algorithmus irgendwie etwas anderes, oder?

q := Kopie von numbers als Queue 
b := Array von 2 Buckets, realisiert als Listen
wiederhole von k := 32 bis 1 {
    leere alle Buckets
    wiederhole so lange q nicht leer ist {
        e := hole und entferne nächstes Element aus q
        s := Darstellung von e als Zeichenkette
        falls das k-te Zeichen von s den Codepoint 0 besitzt, 
            dann füge e zum ersten Bucket hinzu
            sonst zum zweiten Bucket
    }
    füge die Elemente des ersten Bucket zu q hinzu
    füge die Elemente des zweiten Bucket zu q hinzu
}

 

[Heinrich500]

Meinst du
s := Darstellung von e als Zeichenkette?
Aber sonst hätte ich mit den Algorithmus so vorgestellt. Ich verstehe nicht ganz, wie ich das mit der Binärdarstellung der Zahl realisiere.

 

[Meniskusschaden]

Ich verstehe nicht ganz, wie ich das mit der Binärdarstellung der Zahl realisiere.

Folgendes liefert die Zahl 42 als 32-Bit-Binärzahl im String: String.format("%32s", Integer.toBinaryString(42)).replace(' ', '0')

 

[Heinrich500]

Soll ich dann die Zahlen gleich am Anfang beim Kopieren in die Queue umwandeln?

 

[Meniskusschaden]

Soll ich dann die Zahlen gleich am Anfang beim Kopieren in die Queue umwandeln?

Soll die Queue am Ende denn die sortierten Integer enthalten oder die sortierten Strings?

 

[Heinrich500]

Soll die Queue am Ende denn die sortierten Integer enthalten oder die sortierten Strings?

Die sortierten Integer wäre besser.

 

[Meniskusschaden]

Dann müsstest du sie wieder zurück wandeln, wenn du sie schon beim Kopieren umwandelst. Die Queue müsste dann ja Strings anstelle von Integer speichern.

 

[Meniskusschaden]

Du könntest die Umwandlung natürlich auch ganz fallen lassen und direkt auf den Bits der Integer operieren.

 

[mihe7]

Meinst du
s := Darstellung von e als Zeichenkette?
Aber sonst hätte ich mit den Algorithmus so vorgestellt. Ich verstehe nicht ganz, wie ich das mit der Binärdarstellung der Zahl realisiere.

Ja, das und den Vergleich mit Codepoint 0 meinte ich. Ansonsten sollte es passen.

 

[Xyz1]

Ich versteh noch nicht ganz wieso hier eine Zahl in einen String umgewandelt werden muss.

 

[Xyz1]

import java.util.PriorityQueue;
import java.util.Random;

public class BS {

    void sort_bs(int[] a) {
        PriorityQueue<Integer>[] pqs = new PriorityQueue[a.length];
        for (int i = 0; i < pqs.length; i++) {
            pqs[i] = new PriorityQueue<>();
        }

        for (int i : a) {
            int x = (int) ((double) a.length / Integer.MAX_VALUE * i);
            System.out.println(i + " to " + x);
            pqs[x].add(i);
        }

        int i = 0;
        for (PriorityQueue<Integer> pq : pqs) {
            for (Integer in : pq) {
                a[i] = in;
                i++;
            }
        }
    }

    public static void main(String[] args) {
        int[] a = new int[20];
        for (int i = 0; i < a.length; i++) {
            a[i] = new Random().nextInt(Integer.MAX_VALUE);
        }
        (new BS()).sort_bs(a);
    }

}

Bearbeitung:

        int max = 0;
        for (int i : a) {
            if (i > max) {
                max = i;
            }
        }
        max++;

noch einzufügen.

 

[mihe7]

Ich versteh noch nicht ganz wieso hier eine Zahl in einen String umgewandelt werden muss.

Muss ja auch nicht. Die Idee dahinter ist einfach die, Zahlen als binäres Wort fester Länge zu verstehen.

 

[Xyz1]

Muss ja auch nicht. Die Idee dahinter ist einfach die, Zahlen als binäres Wort fester Länge zu verstehen.

Und wie hat das mit Bucket Sort zu tun? Und wie müsste der Algo aussehen? Kommt da am Ende die Laufzeit O(n) heraus? (sorry, für letztere Frage)

 

[mihe7]

Sein Algorithmus passt schon (bis auf die Binärdarstellung/"Bitprüfung").

q := Kopie von numbers als Queue => O(n)
b := Array von 2 Buckets, realisiert als Listen => O(1)
wiederhole von k := 32 bis 1 { => O(1)
    leere alle Buckets => O(1)
    wiederhole so lange q nicht leer ist {  => O(n)
        nächstes Element aus q holen und entfernen und
        gem. des k-ten Bits in das richtige Bucket einsortieren => O(1)
    }
    füge die n-Elemente der beiden Buckets zu q hinzu => O(n)
}

=> Laufzeit in O(n).

 

[Xyz1]

Also wär Sortieren in O(n) für bestimmte Eingaben möglich?

 

[Xyz1]

BTW ich habe 'ne geniale Seite gefunden, konnte aber noch nich alles lesen: https://blog.scottlogic.com/2010/12/22/sorted_lists_in_java.html .

 

[mihe7]

Also wär Sortieren in O(n) für bestimmte Eingaben möglich?

So gesehen schon, allerdings ist das "ein wenig" Augenwischerei. Würde man die konstante Zahl an Wiederholungen z. B. durch log(n) ersetzen, dann hätte man O(n*log(n)) und bis 32 < log(n), also 2^32 < n gilt, sind ein paar Einträge notwendig.

 

[Heinrich500]

Muss ja auch nicht. Die Idee dahinter ist einfach die, Zahlen als binäres Wort fester Länge zu verstehen.

gem. des k-ten Bits in das richtige Bucket einsortieren

Hallo,
vielen Dank für euere Beiträge. Soweit ich verstanden habe, muss ich also die Integers nicht in Strings umwandeln und dementsprechend meine Listentypen auch nicht verändern. Wie kann man nun Zahlen im Code bitweise interpretieren. Das war ja mein Problem von Anfang an.

 

[Heinrich500]

Ich kenne mich mit bit- Operatatoren nicht aus, aber vllt ginge ja folgendes:
Abhängig von k aus der for Schleife gelte:

int component = (int) Math.pow(2,k);

Damit habe ich jeweils in einer Komponente eine 1 sonst 0.
Dann nehme ich ein Element e aus meine Queue und schaue:

if ((e & component) == component)

Dann muss ja das e eine 1 in der k-ten Komponente haben oder?

 

[Xyz1]

Nur macht Dein Algorithmus irgendwie etwas anderes, oder?

@mihe7 Etwas stimmt hier bei Dir nicht, teste das mal bitte:

    void sort_bs(int[] a) {
        ArrayList<Integer> q = new ArrayList<>(Arrays.stream(a).boxed().collect(Collectors.toList()));
        PriorityQueue<String> b = new PriorityQueue<>();
        PriorityQueue<String> c = new PriorityQueue<>();
        for (int k = 31; k >= 0; k--) {
            b.clear(); c.clear();
            while (!q.isEmpty()) {
                String s = String.format("%32s", Integer.toBinaryString(q.remove(0))).replace(' ', '0');
                if (s.charAt(k) == '0') {
                    b.add(s);
                } else {
                    c.add(s);
                }
            }
            for (String s : b) {
                q.add(Integer.parseInt(s, 2));
            }
            for (String s : c) {
                q.add(Integer.parseInt(s, 2));
            }
        }
        for (int i = 0; i < q.size(); i++) {
            a[i] = q.get(i);
        }
    }

Ergebnis: Fast sortiert.

 

[Meniskusschaden]

Wie kann man nun Zahlen im Code bitweise interpretieren.

Dabei sind die Operatoren zur Bit-Manipulationen wie z.B. & und << nützlich.

 

[mihe7]

Etwas stimmt hier bei Dir nicht, teste das mal bitte:

Du darfst keine PriorityQueue verwenden, die Einfügereihenfolge muss beibehalten werden.

 

[mihe7]

Dann muss ja das e eine 1 in der k-ten Komponente haben oder?

Ja, wobei Math.pow(2, k) == (1 << k) gilt und das 1. Bit dem 32. Zeichen der String-Darstellung entspricht.

 

[Xyz1]

Du darfst keine PriorityQueue verwenden, die Einfügereihenfolge muss beibehalten werden.

Mensch mensch, @mihe7 , sach mir das doch...

void sort_bs(int[] a) {
    ArrayList<Integer> q = new ArrayList<>(Arrays.stream(a).boxed().collect(Collectors.toList()));
    ArrayList<String> b = new ArrayList<>();
    ArrayList<String> c = new ArrayList<>();
    for (int k = 31; k >= 0; k--) {
        b.clear(); c.clear();
        while (!q.isEmpty()) {
            String s = String.format("%32s", Integer.toBinaryString(q.remove(0))).replace(' ', '0');
            if (s.charAt(k) == '0') {
                b.add(s);
            } else {
                c.add(s);
            }
        }
        for (String s : b) {
            q.add(Integer.parseInt(s, 2));
        }
        for (String s : c) {
            q.add(Integer.parseInt(s, 2));
        }
    }
    for (int i = 0; i < q.size(); i++) {
        a[i] = q.get(i);
    }
}

Jetzt verstehe ich auch die O(n)-Annahme... (eigentlich kann es nicht mehr als 32*n sein, oder?)

 

[Xyz1]

Du darfst keine PriorityQueue verwenden, die Einfügereihenfolge muss beibehalten werden.

Ich darf schon

        PriorityQueue<String> b = new PriorityQueue<>((String o1, String o2) -> +1);
        PriorityQueue<String> c = new PriorityQueue<>((String o1, String o2) -> +1);

Aber ich will diesen Faden jetzt nicht ad absurdum führen.

 

[Heinrich500]

Ja, wobei Math.pow(2, k) == (1 << k) gilt und das 1. Bit dem 32. Zeichen der String-Darstellung entspricht.

Ich verstehe jetzt nicht ganz was das heißen soll?

 

[mihe7]

(eigentlich kann es nicht mehr als 32*n sein, oder?)

Ja, der Algorithmus durchläuft immer 32*n Iterationen. Da der Faktor 32 konstant ist, ergibt sich O(n).

Die Augenwischerei kommt ja daher, dass ein allgemeiner Sortieralgorithmus praktisch n*log(n) Iterationen durchläuft. Damit dieser allgemeine Algorithmus tatsächlich mehr Iterationen benötigt (und damit echt langsamer wird) als der spezielle hier, müsste das n sehr, sehr groß werden.

Ich verstehe jetzt nicht ganz was das heißen soll?

Das soll heißen, dass Du statt Math.pow(2,k) auch (1 << k) schreiben kannst. Du hast eine 1 und verschiebst diese um k Binärstellen nach links. Mit jeder Verschiebung wird der Wert verdoppelt:

Beispiel

Binär | Dezimal | Operation
 0001 |       1 | << 1
 0010 |       2 | << 1
 0100 |       4 | << 1
 1000 |       8 |

Der zweite Punkt heißt, dass das erste Bit dem letzten Zeichen der Zeichenkette entspricht. Wenn Du aus dem Beispiel die 8 herausgreifst, dann ist dort das vierte Bit gesetzt. In der Zeichenkette "1000" wäre es aber das erste Zeichen. Bei der 1 ist das erste Bit gesetzt, in der Zeichenkette "0001" wäre es das vierte Zeichen.

 

[Xyz1]

sehr groß werden

Ungefähr 4,5 Milliarden. Bis dahin treten andere Probleme auf. ...Danke für die Herleitung.

Bearbeitung: oder e^32.

 

[Heinrich500]

@mihe7: Vielen Dank für deine Hilfe. Jetzt sollte der Algo endlich klar sein
Danke auch den anderen für ihre Beiträge

 

[Xyz1]

@Heinrich500 Was ich meinte... bis 4,5 Milliarden Eingaben ist MergeSort sehr viel schneller als BucketSort und ab 4,5 Milliarden Eingaben sind beide zu langsam. Wenn man sich die Kurven ansieht, dann liegt MergeSort quasi immer auf der x-Achse (benötigt also sehr wenig Zeit)

 

[Heinrich500]

@Tobias-nrw: Ich verstehe was du meinst. Ich habe jetzt auch verstanden, dass Bucketsort im Vergleich zu MergeSort langsammer ist. Es ging mir einfach nur um Übung, nicht um Laufzeit