Sortieraufgabe

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.

Sortieraufgabe
Zur Aufgabe 2.2 vom Blatt 6: das klingt für mich erstmal so, als sollten wir einfach beliebige Zahlen einfüllen und doppelt vorkommende seien erlaubt. Dann frag ich mich aber, warum die Zahlen zwischen 1 und n liegen sollen. Oder sollen wir doch eine zufällige Permutation erzeugen?

Edit: interessanterweise steht diese Einschränkung ∈{1,…n} nur in der deutschen Version des Blatts, in der englischen steht da nichts zu. Von solchen Einschränkungen hängt doch aber die Laufzeit von Quicksort auch ab, oder? Ich mein, wenn wir nur Zahlen zwischen 1 und n zulassen, gibts ja mehr doppelt oder häufiger vorkommende Arrayelemente, was ihn langsam macht …


Kann mir vielleicht jemand sagen, was man unter einem Seedwert versteht ?


http://social.msdn.microsoft.com/Forums/en-US/csharpgeneral/thread/00aad736-9308-4d89-a46b-b0481fa45674
google…


Sollter dieser Seedwert eigentlich im Verlauf inkrementiert werden? Sonst ergeben sich ja für jedes i immer k viele gleiche Ergebnisse. Ist das so gedacht?


Du willst ja eine Vergleichbarkeit haben, aber jedes der k-Arrays sollte verschieden sein, sonst macht es ja keinen Sinn :wink:
Und mit einem Seed kannst du ja beliebig viele „Zufallszahlen“ erstellen.


[quote=Sheep]beliebig viele[/quote]Fast. Laut Wikipedia (http://en.wikipedia.org/wiki/Linear_congruential_generator) ist „beliebig“ ≤ 2³² (glibc), ≤ 2⁴⁸ (java.util.Random) :wink:

Jedenfalls reicht einmal Seed-Setzen, man muss also nicht inkrementieren und neu setzen …

Ich frag mich nur, warum ich mit keiner der vier Kurven (Vergleiche/Schreibzugriffe bei Quick/Mergesort) wirklich nah an die 2 n ln n rankomme (welche müsste es denn sein? Vergleiche beim Quicksort?).
Schreibzugriffe beim Mergesort dürften ja ziemlich genau 2 n lb n sein, das passt auch mit meinen Beobachtungen. Aber zu den anderen Ergebnissen hab ich keine Ahnung, was da eigentlich rauskommen sollte …


Darum habe ich ja „Zufallszahlen“ geschrieben, aber es sind trotzdem mehr als genug :wink:


Dann nimm halt nen anständigen Zufallszahlengenerator… Pseudo-random number generation - cppreference.com


Beliebig viele kriegst du auch damit nicht. Aber mehr, als du brauchen kannst, natürlich.


Hey Leute,
wie kann man in Java den CsvWriter verwenden bei egal was ich im Internet finde, was man dafür einbinde muss funktioniert das nicht. Oder gibt es eine andere Möglichkeit dafür das mit der Csv Datei zu machen?


Schau dir doch einfach mal an, was für Dateien Gnuplot liest. Dann wirst du darauf kommen das es recht, wenn du in eine Datei schreiben kannst und dazu noch ein paar tabs und Zeilenumbrüche machen kannst :wink:


Hat jemand ähnliche oder andere Ergebnisse und kann mir sagen, was ich richtig bzw. falsch mache, dass Quicksort weniger als 2·n·ln n Vergleiche macht? http://wwwcip.cs.fau.de/~iw03enah/kompalg/large.pdf

1 „Gefällt mir“

Hallo,
was ist denn bei der letzen Teilaufgabe(4.) mit Standardabweichung gemeint?


Noch kein Mathe 4 gehört? Wenn du n Werte [;x_1,\dots,x_n;] hast, dann ist die Standardabweichung [;\sqrt{\sum_{i=1}^n(x_i-\bar x)^2};], wobei [;\bar x=\frac1n\sum_{i=1}^nx_i;] das arithmetische Mittel bezeichnet. Siehe auch http://en.wikipedia.org/wiki/Standard_deviation


nope^^

ok vielen Dank.


Also Standardabweichungen hatte ich auch in der Schule… oder wurde das aus dem G8 gestrichen? ô.O


Wir hatten sowas nicht in der Schule (Mathe Grundkurs), wenn ich mich recht erinnere …


War G9ler. Ich hatte das in der Schule nicht gehabt.


Dann war das anscheinend nur LK-Stoff.