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

[jaenicke]

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.

Also, du hast die folgenden Namen:
Martin Schmidt
Adam Schmidt
Martina Abel

Wenn du jetzt nach Nachname sortierst, ist es irrelevant, dass Adam vor Martin kommen würde. Denn danach wird nicht sortiert. Wenn das Suchverfahren stabil ist, belässt es die beiden Einträge in der Reihenfolge, denn da die Nachnamen gleich sind, müssen diese nicht in der Reihenfolge verändert werden.

Ein instabiles Sortierverfahren garantiert nicht, dass diese beiden Einträge danach in der selben Reihenfolge sind, da dort auch Einträge mit gleichen Sortierschlüsseln (in diesem Fall Schmidt als Nachname) ausgetauscht werden können (können, nicht müssen).

[Bjoerk]

Auf alle Fälle auf die wohl Eingangsfrage des Fremdprüfers antworten können, was der Unterschied zwischen numerischer und alphanumerischer Sortierung ist. :wink:

1
2
3
4
5
6
7

1
10
100
11
12
13
2
20

[himitsu]

Wenn mit den zu sortierenden Daten noch weitere Daten verknüpft sind, wie z.B. irgendwelche Objekte oder Sonstwas,
dann kann es schon relevant sein, daß diese Zusatzdaten in einer gewissen Reihenfolge verbleiben, wenn ihre ihre zugeordneten Sortierdaten den gleichen Wert haben.

[p80286]

Folgende Daten sind zu sortieren:

Muller, albert 043134
Müller, alfred 012345
Müller, alfred 043134
Müller, Monika 043134
Müller, Xaver 012345

Sortierschlüssel ist die PLZ

Müller, alfred 012345
Müller, Xaver 012345
Muller, albert 043134
Müller, alfred 043134
Müller, Monika 043134

Das ist vor allem interessant wenn mehrere Sortierläufe nacheinander gebraucht werden.
(man kann natürlich auch den Schlüssel entsprechend wählen, aber bei großen datenmengen ist es schon hilfreich)

Gruß
K-H

[Bjoerk]

Zitat:

Ein instabiles Sortierverfahren garantiert nicht, dass diese beiden Einträge danach in der selben Reihenfolge sind, da dort auch Einträge mit gleichen Sortierschlüsseln (in diesem Fall Schmidt als Nachname) ausgetauscht werden können (können, nicht müssen).

Hallo jaenicke,

check ich au nicht. Würde das nicht bedeuten, daß der Operator unzuverlässig arbeitet?

entweder ich möchte es

Delphi-Quellcode:

  for I:= 0 to Count-2 do
    for J:= I+1 to Count-1 do
      if Item[I] > Item[J] then Exchange(I, J);

oder so

Delphi-Quellcode:

  for I:= 0 to Count-2 do
    for J:= I+1 to Count-1 do
      if Item[I] >= Item[J] then Exchange(I, J);

[himitsu]

Nein, würde es nicht.

Es kommt darauf an, in welcher Reihenfolge die Items verglichen und wie sie umgruppiert werden.

Es hängt also vom Zugriffsmuster und der Vergleichsauswertung des Sortierverfahrens ab ... darum sind auch Einige stabil und Andere nicht.

[Luckie]

Zitat:

Zitat von jaenicke (Beitrag 1104168)

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.

Also, du hast die folgenden Namen:
Martin Schmidt
Adam Schmidt
Martina Abel

Wenn du jetzt nach Nachname sortierst, ist es irrelevant, dass Adam vor Martin kommen würde. Denn danach wird nicht sortiert. Wenn das Suchverfahren stabil ist, belässt es die beiden Einträge in der Reihenfolge, denn da die Nachnamen gleich sind, müssen diese nicht in der Reihenfolge verändert werden.

Ein instabiles Sortierverfahren garantiert nicht, dass diese beiden Einträge danach in der selben Reihenfolge sind, da dort auch Einträge mit gleichen Sortierschlüsseln (in diesem Fall Schmidt als Nachname) ausgetauscht werden können (können, nicht müssen).

Danke, sehr schön erklärt.

[Sir Rufo]

Wir haben eine Artikelliste mit folgenden Spalten

Code:

Warenhauptgruppe
Warenuntergruppe
Lieferant
Artikelnummer

und diese möchte ich auch in der Reihenfolge sortiert haben.

Ein instabiles Sortierverfahren müsste jetzt alle 4 Kriterien gleichzeitig berücksichtigen um die gewünschte Sortierung herzustellen.

Bei einem stabilen Sortierverfahren sortiert man die Felder in umgekehrter Reihenfolge.
Also erst mal nach den Artikelnummern, dann Lieferant, Warenuntergruppe, Warenhauptgruppe.
(z.B. in Excel werkelt so ein stabiles Sortierverfahren)

Meine Vermutung (so aus der Hüfte geschossen):

Ein stabiles Sortierverfahren ist aufwendiger in der Programmierung, langsamer in der Ausführung, aber in der Handhabung einfacher als das instabile Sortierverfahren.

[Stevie]

Zitat:

Zitat von Sir Rufo (Beitrag 1104238)

Meine Vermutung (so aus der Hüfte geschossen):

Ein stabiles Sortierverfahren ist aufwendiger in der Programmierung, langsamer in der Ausführung, aber in der Handhabung einfacher als das instabile Sortierverfahren.

Bin kein Experte, was Sortieralgos angeht, aber wenn ich mir die Liste anschaue, würd ich sagen: nö

[Sir Rufo]

Zitat:

Zitat von Stevie (Beitrag 1104242)

Zitat:

Zitat von Sir Rufo (Beitrag 1104238)

Meine Vermutung (so aus der Hüfte geschossen):

Ein stabiles Sortierverfahren ist aufwendiger in der Programmierung, langsamer in der Ausführung, aber in der Handhabung einfacher als das instabile Sortierverfahren.

Bin kein Experte, was Sortieralgos angeht, aber wenn ich mir die Liste anschaue, würd ich sagen: nö

Dann hat sich der Colt beim Ziehen wohl verhakt :mrgreen: