[JAVA]Reiskörner berechnen

willikufalt · 19.10.2010

Mergesort ist eigentlich recht einfach zu verstehen und auch zu implemtieren:
http://de.wikipedia.org/wiki/Mergesort

Mergesort arbeitet im besten, durchschnittlichen und schlechtesten Fall optimal.
(Zeitkomplexität O(n* log(n))

Auch einfach zu implementieren ist eigentlich Shellsort.
http://de.wikipedia.org/wiki/Shellsort <---- Hier ist auch Java-Code enthalten.

Auch von der Laufzeit her ist Shellsort nicht schlecht.
Allerdings ist Shellsort theoretisch ziemlich schwer zu verstehen.

Jakob · 20.10.2010

Ok, dann probiere ich Mergesort.
Aber gleich die erste Frage:
So fange ich ja an: void mergesort(int links, int rechts)
Was muss ich denn hier "links" und "rechts" zuweisen? Es geht doch hier eigentlich erstmal nur um die Länge des Arrays, damit das geteilt weden kann, oder? Aber welche Werte müssen "links" und "rechts" dann haben?

FerFemNemBem · 20.10.2010

Halloechen,

steht doch dort im (Pseudo)Code. Wenn die Liste mehr als 1 Elemente enthaelt, teilst Du sie in 2 Listen auf. Dann hast Du eine linke und eine rechte Liste.

Gruss, FFNB.

Jakob · 20.10.2010

Ja, aber welche Werte bzw. wie teile ich der rechten und linken Liste die zugehörigen Werte zu?
Wenn ich jetzt das Array a habe und das 10 Felder hat, kann ich es ja nach a[4] teilen. Also bis a[4] wäre der linke Teil und ab a[5] der rechte. Aber wie weise ich das jetzt der Variablen links oder rechts zu?

cmddegi · 20.10.2010

Das Problem ist, dass die Parameter in deinem Funktionskopf int's sind, also einfache Zahlen. Du brauchst aber Listen von Zahlen. Du könntest also stattdessen z.B. Arrays übergeben. Oder du machst die "unschöne" Variante mit einem globalen Array als Liste, und übergibst deiner Funktion nur die Indizes im Array (und ggfs. Längen der Listen, falls benötigt).

Jakob · 20.10.2010

Und wie funktioniert das mit dem Arrays übergeben? Müsste ich dann vorher schon 2 Arrays anlegen, die ich schon aufgeteilt habe oder wie mache ich das?

cmddegi · 20.10.2010

Hier sollte alles notwendige stehen:
http://www.programmersbase.net/Content/Java/Content/Tutorial/Java/Array.htm

willikufalt · 20.10.2010

Hier noch eine interessante Seite mit Java-Code:

http://www.miaowang.de/studium/tutorials/applets/mergesort_de.html

Jakob · 22.10.2010

Ich habe jetzt nochmal den Algorithmus von Shakersort genommen und habe das auch zum Laufen bekommen. Allerdings stellt sich mir noch die Frage: Wird Shakersort noch als Bubblesort angesehen oder ist es ein eigenes Sortierverfahren? Ich würde meinen Lehrer fragen, aber das geht erst ab Montag, da noch Ferien sind. Wenn ihr mir schon sagen könnt, dass es kein eigenständiges Verfahren ist, kann ich jetzt schon weitersuchen...

Jakob · 22.10.2010

Noch eine Frage:
Was ist an dem Code für Insertionsort falsch?

Code:

  public void insertion() {
        int raus;
        int j;
        for (int i=1;i<anzahl;i++) {              //äußere Schleife : 2. Element aus Feld raus
            raus=zahlen[i];
            //schieben
            for (j=i-1  ;zahlen[j]>raus;j--) {         // innere: sortieren; i-1 -> links neben i
                zahlen[j+1]=zahlen[j];
            };
            zahlen[j+1]=raus; //rausgenommenes ins Loch     //äußere Schleife : 2. Element rein
        }
    }

Es kommt damit immer die Fehlermeldung

Exception in thread "AWT-EventQueue-0" java.lang.ArrayIndexOutOfBoundsException: -1
at Sortieren.insertion(Sortieren.java:161)
at Sortierverfahren.button1_ActionPerformed(Sortierverfahren.java:80)
at Sortierverfahren$2.actionPerformed(Sortierverfahren.java:63)
at java.awt.Button.processActionEvent(Button.java:392)
at java.awt.Button.processEvent(Button.java:360)
at java.awt.Component.dispatchEventImpl(Component.java:4630)
at java.awt.Component.dispatchEvent(Component.java:4460)
at java.awt.EventQueue.dispatchEvent(EventQueue.java:599)
at java.awt.EventDispatchThread.pumpOneEventForFilters(EventDispatchThread.java:269)
at java.awt.EventDispatchThread.pumpEventsForFilter(EventDispatchThread.java:184)
at java.awt.EventDispatchThread.pumpEventsForHierarchy(EventDispatchThread.java:174)
at java.awt.EventDispatchThread.pumpEvents(EventDispatchThread.java:169)
at java.awt.EventDispatchThread.pumpEvents(EventDispatchThread.java:161)
at java.awt.EventDispatchThread.run(EventDispatchThread.java:122)

cmddegi · 22.10.2010

Ich würde mal sagen, j wird negativ. In dieser Zeile

Code:

for (j=i-1  ;zahlen[j]>raus;j--) {

wird j immer verringert und die einzige Schleifenbedingung ist, dass zahlen[j] größer als raus ist. Wenn die Abbruchbedingung nicht eintritt, versucht er irgendwann, auf zahlen[-1] zuzugreifen, was nicht geht.

Jakob · 22.10.2010

Ok, Danke Dir nochmal.
Habe jetzt die Quelltexte von Insertion- und Shakersort und sie scheinen zu funktionieren

.
Dann werde ich morgen die beiden dann vergleichen und dazu einen Text verfassen...

[JAVA]Reiskörner berechnen

willikufalt

Jakob

FerFemNemBem

Jakob

cmddegi

Jakob

cmddegi

willikufalt

Jakob

Jakob

cmddegi

Jakob

[JAVA]Reiskörner berechnen

ANGEBOTE & SPONSOREN

Neueste Beiträge

Statistik des Forums