Zufallszahlen / Sortierverfahren

[jaenicke]

Zitat von 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.

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.

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 von jaenicke:

Zitat von 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.

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 von Sir Rufo:

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 von Stevie:

Zitat von Sir Rufo:

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