Dies ist eine statische Kopie unseres alten Forums. Es sind keine Interaktionen möglich.
This is a static copy of our old forum. Interactions are not possible.

migu

free rider

  • "migu" is male
  • "migu" started this thread

Posts: 2,643

Date of registration: Dec 11th 2001

Occupation: Developer

1

Tuesday, May 14th 2002, 9:26pm

Java: Fehler in 4. Aufgabe

Heute Nachmittag habe ich Aufgabe 4 bearbeitet. Nach ein paar kleinen Schwierigkeiten lief das Programm und sortierte die eingegebene Liste.

Wenn aber ein Element mehr als einmal in der Liste vorkommt, hängt sich der Soriertalgorithmus (Quicksort) auf und kommt nicht zum Ende.

Thomas Bessey war gerade in F411 und konnte sich das Problem ansehen. Resultat: Ein kleiner Fehler in der Aufgabenstellung, der bewirkt, dass Quicksort nur im Spezialfall arbeitet, dass die Liste nur verschiedene Elemente enhält.

Auf dem Aufgabenblatt wurde deshalb der Hinweis hinzugefügt:
Achtung: Der o.a. Algorithmus erlaubt keine zwei gleichen Objekte im Array!
(Das alte Aufgabenblatt findet ihr unter http://cgan.de/uni/doc/Aufgabe04.pdf.)

Also, implementiert das Programm ruhig, aber wunder euch nicht, und wenn ihr euch wundert, dann behebt den Fehler. ;) :)
Ich für meinen Teil habe mir vorhin aus der TIB das bekannte Buch "Algorithmen" von Robert Sedgewick entliehen. Es wird mir bei der korrekten Implementation von Quicksort helfen. :)

Happy coding!
tar: Anlegen eines leeren Archivs wird feige verweigert.
  • Send private message

MAX

Senior Schreiberling

  • "MAX" is male

Posts: 822

Date of registration: Dec 11th 2001

Location: Hannover

2

Wednesday, May 15th 2002, 7:36pm

Verständnisproblem

Hallo!!!
Ich habe da eine Frage. In der Aufgabe steht: "Wenn i kleiner als j ist, vertausche die Objekte mit den Indizes i und j."
Was soll da genau vertauscht werden? Zwei Objekte oder nur die Werte der Indizes? (Kapiere nicht ganz)
Dann noch sollen wir das Array objects nochmal sortieren. Wozu das denn? Wird es nicht vorher schon gemacht?
mfg
MAX

die Aufgabenstellung etwas komisch findend
  • Send private message

RoKu

Trainee

  • "RoKu" is male

Posts: 89

Date of registration: Dec 17th 2001

Location: Lehrte/Europa

Occupation: Informatiker ohne Diplom

3

Wednesday, May 15th 2002, 7:45pm

Quoted

Ich habe da eine Frage. In der Aufgabe steht: "Wenn i kleiner als j ist, vertausche die Objekte mit den Indizes i und j."
Was soll da genau vertauscht werden? Zwei Objekte oder nur die Werte der Indizes? (Kapiere nicht ganz)


Es geht um folgendes:

Du hast in Deiner methode sort(Object[], int, int) ein Object Array als Aktualparamter übergeben bekommen.
Beispiel:

Sei objs ein Objectarray
dann vertauscht man z.b. folgendermassen:
objs=objs[j]

Vorsicht, man sollte sich objs[i] vorher sichern, damit man es wieder an die Stelle objs[j] setzen kann.


Hier werden also die "Werte" bzw. Objecte vertauscht.

Den Q-Sort hier zu erkären....ist kompliziert....und sehr anspruchsvoll.

Es ist nicht wichtig zu verstehen warum gerde so sortiert wird, und warum das so funktioniert.
Gruß,

Rolf

"verba volant, scripta manent (discussions get forgotten, just code remains)"
  • Send private message

Joachim

Guru

  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

4

Wednesday, May 15th 2002, 8:17pm

Quoted

Original von RoKu
Den Q-Sort hier zu erkären....ist kompliziert....und sehr anspruchsvoll.
Für die, die's trotzdem wissen wollen, habe ich mal ein paar Websites rausgesucht:

http://n.ethz.ch/student/fzlatko/Quicksort.htm
http://www.cis.ufl.edu/~ddd/cis3020/summ…lectures/lec17/
http://www.uni-karlsruhe.de/~za714/mater…rs12/sort5.html



... oder man schaut (falls Interesse an Sortieralgorithmen im allgemeinen besteht) in das Buch der Bücher zu diesem Thema:

Donald E. Knuth: "The Art of Computer Programming - Volume 3: Sorting and Searching"
The purpose of computing is insight, not numbers.
– Richard Hamming, 1962
  • Send private message

MAX

Senior Schreiberling

  • "MAX" is male

Posts: 822

Date of registration: Dec 11th 2001

Location: Hannover

5

Wednesday, May 15th 2002, 8:43pm

Danke

Quoted

Sei objs ein Objectarray
dann vertauscht man z.b. folgendermassen:
objs=objs[j]

Vorsicht, man sollte sich objs[i] vorher sichern, damit man es wieder an die Stelle objs[j] setzen kann.

So habe ich mir auch gedacht, kennt man halt aus der Schule. Nur die Formulierung hat mich etwas verwirrt.

Quoted

Hier werden also die "Werte" bzw. Objecte vertauscht.

Den Q-Sort hier zu erkären....ist kompliziert....und sehr anspruchsvoll.

Es ist nicht wichtig zu verstehen warum gerde so sortiert wird, und warum das so funktioniert.

Dann ist ja gut. Ich habe mir schon gedacht: Ehh???

Quoted

Für die, die's trotzdem wissen wollen, habe ich mal ein paar Websites rausgesucht:

http://n.ethz.ch/student/fzlatko/Quicksort.htm
http://www.cis.ufl.edu/~ddd/cis3020/summ...lectures/lec17/
http://www.uni-karlsruhe.de/~za714/mater...rs12/sort5.html


Das ist eine schöne Hilfe! Danke!!!

mfg
MAX
  • Send private message

RoKu

Trainee

  • "RoKu" is male

Posts: 89

Date of registration: Dec 17th 2001

Location: Lehrte/Europa

Occupation: Informatiker ohne Diplom

6

Thursday, May 16th 2002, 1:55pm

Quoted

Donald E. Knuth: "The Art of Computer Programming - Volume 3: Sorting and Searching"


Dieses Buch ist natürlich hervorragend.

Wer grundsätzlich ein gutes Buch zu Algorithmen lesen möchte, dem sei dieses Buch empfohlen:

R.Sedgewick "Algorithmen"
mit vielen Code-Beispielen in versch. Programmiersprachen.
Gruß,

Rolf

"verba volant, scripta manent (discussions get forgotten, just code remains)"
  • Send private message

luzifah

Trainee

  • "luzifah" is male

Posts: 64

Date of registration: Jan 6th 2002

Location: Laatzen

7

Monday, May 20th 2002, 2:21pm

moin,

kurze Frage:

mein prog funzt soweit ich bin mir nur nicht sicher mit dem IllegalArgumentExeption reicht es zu sagen:
<br>
public static Comparable[] sort(Comparable[] a) throws IllegalArgumentException { ... } ??
<br> oder was ist denn ein Illegales Argument zum testen ?

thx und schoene freie Tage noch :)
... rebooting is for adding new hardware...
  • Send private message

Zypressen Hügel

Junior Schreiberling

Posts: 244

Date of registration: Dec 22nd 2001

8

Monday, May 20th 2002, 3:08pm

Quoted

public static Comparable[] sort(Comparable[] a) throws IllegalArgumentException { ... } ??


müsste so reichen, hab ich auch so. natürlich muss noch eine schleife o.ä. eingebaut werden, die dann tatsächlich die ausnahme wirft, wenn die argumente nicht comparable sind.

zum testen wäre, je nachdem wie man die testschleife aufbaut, ein vergleich eines Integer und eines String ganz gut oder einfach ein JButton oder so was ähnliches aus den awt/swing-klassen. da kann man sich eigentlich sicher sein, dass die nicht comparable sind und sich gut zum testen eignen.
Man kann auch ohne Spass Alkohol haben 8)
  • Send private message

migu

free rider

  • "migu" is male
  • "migu" started this thread

Posts: 2,643

Date of registration: Dec 11th 2001

Occupation: Developer

9

Monday, May 20th 2002, 9:34pm

Quoted

Original von Zypressen Hügel
zum testen wäre, je nachdem wie man die testschleife aufbaut, ein vergleich eines Integer und eines String ganz gut oder einfach ein JButton oder so was ähnliches aus den awt/swing-klassen. da kann man sich eigentlich sicher sein, dass die nicht comparable sind und sich gut zum testen eignen.


jawoll

Ein legales Argument ist ja genau genommen eine Instanz einer Klasse, die das Interface Comparable implementiert. Alles andere soll zurückgewiesen werden.
In der API-Doku steht zu jeder Klasse, wovon sie abgeleitet ist und ob oder welches Interfaces sie implementiert.

Ich hatte mir mal eine eigene Klasse geschrieben, die nicht Comparable implementiert. Ist ja einfach. Da konnte ich mal sehen, wie das aussieht, wenn sort(Object[]) die IllegalArgumentException wirft. :)
tar: Anlegen eines leeren Archivs wird feige verweigert.
  • Send private message