Aufgabe 12.1

Bachelor Algorithmen und Datenstrukturen
1

Sortieralgorithmen

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

2

Aufgabe 12.1
Also, generell muss ich sagen, dass das Blatt eigentlich ziemlich einfach ist! Sollte wohl machbar sein!

Gerade die Sortieralgorithmen machen sich mit links und außerdem stehen sie auf den Folien (die bisher noch net online sind…)!

Dummerweise sitz ich jetzt hier und mach ein Testcaseprogramm (ein Blick auf die Uhr verrät mir, dass ich bescheuert bin :motz: )! Leider berechnet es jetzt auch die Zeiten, deswegen will ichs nicht ohne weiteres hier ins Forum stelln. "Denkt doch selber mal :smiley: "

Wers will, sagt bescheid!

3

andere frage: habe eben schnell mal quicksort gemacht aber ich weiss nicht…kontruktor??? wird da mal irgendwann auch die sortierte liste zurückgegeben?

4

Die sortierte Liste muss nicht zurückgegeben werden, weil alle Aktionen direkt auf die (als Referenz) übergebene Liste angewendet werden können.
Und Konstruktor brauchst du auch keinen, sofern du keine Instanzvariablen in deiner Klasse verwendest.

5

Und lest euch mal die Aufgabenstellung genau durch.
Mann soll drei der vier Algorithmen implementieren.

Aber auf der Seite fehlt der Quicksort in Fortran.

6

Das hast du aber schlau geschlussfolgert :moody:

7

Also, jetzt hab ichs doch noch geschafft das Programm “euch”-tauglich zu machen. Heißt so viel, es muss der Code nicht verändert werden. Also hab ich mir jetzt gedacht, stell ichs mal online, da könnt ich es enschlüssen und decodieren wenn ihr so *** drauf seid!

Ich würde halt, für den Theorieteil meinen, ihr programmiert die Messung trotzdem mal, weil ich habs ja nur für nen beschissenen Wert von 20000 Elementen gemacht!

Wie immer, einfach ins selbe Verzeichniss wie die Sortierungsklassen!

Viel Spaß damit!

Attachment:
SortTest.class: https://fsi.cs.fau.de/unb-attachments/post_31300/SortTest.class

8

Hi,

mal ne dumme Frage: Ich hab jetzt mal SelectionSort und BubbleSort schnell geschrieben, funktioniert soweit auch wunderbar, also er sortiert die Eingaben aufsteigend. Wie gebt ihr denn die Werte ein? Ich hab einfach mal Integer genommen, weil Integer ja Comparable implementiert. Aber der Tescase gibt mir trotzdem nur 5%, also quasi sagt er ich sortier gar net, oder völlig falsch, die Reihenfolge stimmt aber…

Bin ich völlig bescheuert? Ich check net wirklich was ich falsch mach, der soll doch einfach alles was comparable is, sortieren oder?

Könnt ihr mir vielleicht nen Tip geben?

9

Hm… also generell muss ich sagen, ich hab keine Erfahrung mit Fehlern gemacht. Habs geschrieben, hoch geladen, 100%…

Ähm, so public probleme? Wird auch wirklich das richtige sortierte Array übergeben? und es is sicher kein neues Array, sondern die Elemente des übergebene Array wurden überschieben?

Wenns bei dir mit nem Int geht, dann gehts mit jedem, deswegen ja Comparable… du hasts doch mit compareTo geschrieben oder?

Naja, wenn das nicht hilft… dann schick mir mal deinen code!

Bis dann

10

Naja bei der SelectionSort nehm ich halt die Elemente langsam aus dem gegebenen Array raus und schreibs in eine temporäres neues Array, ich könnts auch direkt im gegebenen Array rumschieben, aber dann ist es ja nicht mehr wirklich SelectionSort. Danach schreib ich die temporäre sortierte Liste dann zurück ins gegebene Array… Dies tu ich extra mit clone, dass auch wirklich die Elemente im gegebenen Array stehn und nicht nur irgendwie die Referenz umgebogen wird… sehr komisch…

11

Das clone ist denk ich genau der fehler. Ich hab jedes Element aus dem Tempory auf das Element der Übergebenen List gesetzt. Also quasi gerade nur die Zeiger umgebogen.

...
list[i]=tmp[i];
...
12

Hi,

erstaunlich, du hattest recht. Ich brauche nicht clone sonder Sysetm.arrayCopy jetzt gehts… Danke!

13

hat denn jmd schon irgendwelche runtimes für 100 000 elemente?? rein rechnerisch würde doch der selection oder bubble sort so um die 40 stunden dauern!!? :vogel: ganz so lang will ich das eigentlich nicht laufen lassen…

[edit: bei 1000 braucht mein selsort 118ms]

14

Also bei mir braucht der SelectionSort für 1000 Elemente 19 ms… für 100000 ergeben sich dann knapp 6 Minuten…

Darf man das Ding eigentlich ein bisschen optimieren? Ich hätt da so n paar Ideen, wie ich die Laufzeit drastisch senken könnte…

15

Na klar darfst du optimieren.
Aber eben nicht so, dass aus dem Selectionsort ein Quicksort wird :slight_smile:

Ich hab bei meinen Messungen auch mal den Test mit java.util.Arrays.sort gemacht.
Dreck ist das schnell.

Arraygroesse 10000000
MergeSort		74297 ms	59257 ms	61940 ms	74168 ms	64576 ms
	Durchschnitt 66847 ms
java.util.Arrays.sort	37872 ms	30538 ms	30714 ms	29389 ms	28970 ms
	Durchschnitt 31496 ms

Bubblesort hab ich mal rausgenommen … :slight_smile:

16

kann mir bitte jemand sagen, wie wir diese ganzen algorithmen implementieren sollen (dürfen)! mit gewöhnlichen arrays oder verkettete Listen?

17

hab grade meine drei Sorts hochgeladen- hab einmal 0%, einmal 5% und einmal 100%… das nervt! :motz:

Edit: hab den zweiten auf 100% gekriegt(wobei- nichts geändert, einfach nochmal hochgeladen), aber für BubbleSort gibt er 0% :vogel: ich lass es lieber so, will keine zeit für sowas verschwenden…

18

Na, da hat wohl einer das Aufgabenblatt nicht korrekt gelesen.
Es gibt doch ein nettes Interface von welchem alle deine Sortierklassen abgeleitet werden sollen.
Dieses Interface gibt dir eine Funktion vor welche als Parameter ein Array mit Comparable hat.

Also warum diese Frage?
Sicherlich kannst du alles aus dem Array in eine List und erst mal per Satelit zum Mond schicken - hauptsache du sortierst das Array!

19

gut. danke. dann ist mir alles klar und werde ich die möglichkeit mit dem mond in erwägung ziehen.

20

Aber du weißt, dass die Sache mit dem Mond die Laufzeit doch exterm verlängert.