Zufallszahlen / Sortierverfahren

[Michelle]

Hallo liebe Delphianer!

Ich habe bald meine mündliche Abiprüfung in Informatik. Schwerpunkt wird sein: Simulationen durch Zufallszahlen und Sortierverfahren. Dazu zwei Fragen:

1.) initialization randomize
Wofür genau brauche ich das? Damit wird das Random initialisiert, weil ansonsten der erste Wert von Random immer gleich ist. Irgendwie hängt das wohl mit der Erstellung der Pseudozufallszahlen mithilfe der Systemuhr zusammen, aber wie genau funktioniert das?

2.) instablile Sortierverfahren
Bei stabilen Sortierverfahren behalten Datensätze mit gleichem Schlüsselwort ihre Reihenfolge bei (kann man das so sagen?). Aber was genau sind instabile Sortierverfahren?
Bei MergeSort z.B. weiß man ja nicht, wie die Datensätze mit gleichem Schlüsselwort sortiert sind, das ist quasi zufällig (jedenfalls wenn ich das richtig verstanden habe).
Bei Selectionsort ist das nicht zufällig, da sind die Datensätze mit gleichem Schlüsselwort in umgekehrter Reihenfolge sortiert.
Ist Selectionsort auch ein instabiles Sortierverfahren, oder müssen die Datensätze mit gleichem Schlüsselwort in zufälliger Reihenfolg sortiert sein, damit es ein instabiles Verfahren ist?

Oh je, so viel Text für zwei simple Fragen, sorry!
Wenn ich etwas ungeschickt ausgedrückt habe, dann korrigiert das bitte, für die Prüfung brauch ich ein bisschen Fachsprache :)

Ich hoffe, ich hab euch nicht zu sehr zugetextet! Vielen Dank für euer Interesse an diesem Thema und hoffentlich auch vielen Dank für eure Antworten!!

Liebe Grüße,
Michelle

[himitsu]

1.
Bei Fragen könnte man doch auch mal die Suchfunktion nutzen oder in der OH nachlesen?
Randomize und Randomize

dann findet man z.B. sowas
http://docwiki.embarcadero.com/VCL/de/System.Randomize (englisch: http://docwiki.embarcadero.com/VCL/en/System.Randomize)
http://www.delphipraxis.net/89462-ra...er-zufall.html
http://www.delphipraxis.net/104183-r...s-starten.html
http://www.delphipraxis.net/158670-randomize-o-o.html

Wobei du die Lösung doch schon gesagt hast

Zitat:

Damit wird das Random initialisiert, weil ansonsten der erste Wert von Random immer gleich ist.

Delphi nutzt einen Pseudozufallszahlengenerator.
Dieser "errrechnet" eine Folge von Zahlen und wenn man das nicht initialisiert, dann startet es "immer" mit dem Selben Wert und liefert dann auch die selben Zahlenfolgen.
> siehe RandSeed

Aber bevor das jetzt wer für Verschlüsselungen o.Ä. nutzen will, dann sollte er/sie auch mal da oben reinlesen, denn es kann gut sein, daß irgendwann mal die Berechnung und damit auch die Zahlenfolgen geändert werden.



2:
Bei nichtstabilen Sortierverfahren bleibt (eventuell) die Reihenvolge gleicher Einträge nicht gleich.
Einträge mit dem selben Wert sind dann sortiert schonmal in einer anderen Reihenfolge, wie sie vor der Sortierung standen.
Bei stabilen Verfahren bleibt ihre Reihenfolge gleich.

[Michelle]

1. Wie genau funktioniert das mit der Systemuhr? Ist mit System Delphi oder der PC (das Betriebssystem) gemeint?

2. Wenn man weiß, dass das Sortierverfahren die Datensätze mit gleichem Schlüsselwort in genau umgekehrter Reihenfolge sortiert, ist es dann stabil oder instabil?

3. Vielen Dank für die Antwort :)

[p80286]

Hallo Michelle,

warum bemühst Du nicht die Wikipedia?

Zitat:

Ein stabiles Sortierverfahren ist ein Sortieralgorithmus, der die Reihenfolge der Datensätze, deren Sortierschlüssel gleich sind, bewahrt.

http://de.wikipedia.org/wiki/Stabiles_Sortierverfahren

Was nicht stabil ist.....

Gruß
K-H

[himitsu]

1: Früher (also z.B. noch in Delphi 7) wurde GetTickCount für die Initialisierung genutzt,
aber aktuell wird QueryPerformanceCounter genutzt.

Grund: Aus Sicht des Randomize-Aufrufs ist dieses schon ein Zufallswert, welcher zur Initialisierung des Pfeudizufallsgenerators genutzt wird, da es sehr unwahrscheinlich ist, daß dieses immer genau zur selben Zeit, nach dem Booten des Rechners, aufgerufen wird.



QueryPerformanceCounter wird nun bestimmt vorallem wegen der Idioten genutzt, welche Randomize zu oft aufrufen. :stupid:

[Michelle]

Hallo!

Wikipedia hatte ich schon bemüht, bevor ich die Frage gestellt. Beim Lesen von dem Artikel ist bei mir die Frage ja erst entstanden.
Beim Beispiel von Wiki klang es so, als müsste die Reihenfolge hinterher zufällig sein. Ich habe ein Sortierverfahren, was genau die umgekehrte Reihenfolge liefert. Stabil ist es insofern, als das ich weiß, in welcher Reihenfolge es rauskommt. Instabil ist es insofern, als das die Reihenfolge vorher und hinterher nicht die selbe ist.
Ist es jetzt stabil oder instabil (oder halbstabil)?

[p80286]

Es ist nicht stabil.

Gruß
K-H

[Michelle]

Dankeschöön :thumb:

[Luckie]

Zitat:

Ein stabiles Sortierverfahren ist ein Sortieralgorithmus, der die Reihenfolge der Datensätze, deren Sortierschlüssel gleich sind, bewahrt.

Das verstehe ich nicht. Kann mir das mal bitte jemand erläutern? Vielleicht auch an einem Beipsiel.

[Coffeecoder]

Zitat:

Zitat von Luckie (Beitrag 1104163)

Zitat:

Ein stabiles Sortierverfahren ist ein Sortieralgorithmus, der die Reihenfolge der Datensätze, deren Sortierschlüssel gleich sind, bewahrt.

Das verstehe ich nicht. Kann mir das mal bitte jemand erläutern? Vielleicht auch an einem Beipsiel.

Soweit wie ich das jetzt verstanden haben ist ein Sortierschlüssel z.b. ein Index von einem array.
Siehe auch hier