Sortieralgorithmus

H

Heinrich500

Bekanntes Mitglied
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:
Java: 
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?
 
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?
 
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.
 
Nur macht Dein Algorithmus irgendwie etwas anderes, oder?

Code: 
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
}
 
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.
 
Java: 
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:
Java: 
        int max = 0;
        for (int i : a) {
            if (i > max) {
                max = i;
            }
        }
        max++;
noch einzufügen.
 
Zuletzt bearbeitet von einem Moderator:
Sein Algorithmus passt schon (bis auf die Binärdarstellung/"Bitprüfung").

Code: 
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).
 
mihe7 hat gesagt.:
Muss ja auch nicht. Die Idee dahinter ist einfach die, Zahlen als binäres Wort fester Länge zu verstehen.
Zum Vergrößern anklicken....
mihe7 hat gesagt.:
gem. des k-ten Bits in das richtige Bucket einsortieren
Zum Vergrößern anklicken....
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.
 
Ich kenne mich mit bit- Operatatoren nicht aus, aber vllt ginge ja folgendes:
Abhängig von k aus der for Schleife gelte:
Java: 
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:
Java: 
if ((e & component) == component)
Dann muss ja das e eine 1 in der k-ten Komponente haben oder?
 
mihe7 hat gesagt.:
Nur macht Dein Algorithmus irgendwie etwas anderes, oder?
Zum Vergrößern anklicken....
@mihe7 Etwas stimmt hier bei Dir nicht, teste das mal bitte:
Java: 
    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.
 
mihe7 hat gesagt.:
Du darfst keine PriorityQueue verwenden, die Einfügereihenfolge muss beibehalten werden.
Zum Vergrößern anklicken....
Mensch mensch, @mihe7 , sach mir das doch... 😕
Java: 
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?)
 
mihe7 hat gesagt.:
Du darfst keine PriorityQueue verwenden, die Einfügereihenfolge muss beibehalten werden.
Zum Vergrößern anklicken....

Ich darf schon 😉
Java: 
        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.
 
Tobias-nrw hat gesagt.:
(eigentlich kann es nicht mehr als 32*n sein, oder?)
Zum Vergrößern anklicken....
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.

Heinrich500 hat gesagt.:
Ich verstehe jetzt nicht ganz was das heißen soll?
Zum Vergrößern anklicken....
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
Code: 
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.
 
@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)
 

Aktuelle Jobs

Neue Themen

Ähnliche Themen

Eigener Sortieralgorithmus
Antworten: 3
Sortieralgorithmus
Antworten: 10
Sortieralgorithmus
Antworten: 8
Schleifeninvariante bei Sortieralgorithmus
Antworten: 3
Sortieralgorithmus graphisch darstellen
Antworten: 6

Zurück
Oben