Natürlichkeit bei Sortieralg. < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:05 Mi 01.08.2007 | | Autor: | RalU |
| Aufgabe | Hallo!
Wer kann mir sagen, wann ein Sortierverfahren "natürlich" ist?
Gibt es eine klare Definition von "Natürlichkeit" in Bezug auf Sortieralgorithmen? |
Laut bisherigen Erfahrungen denke ich, dass ein Sortierverfahren natürlich ist, wenn eine gewisse Vorsortierung vorliegt. Allerdings wäre das ja keine eindeutige Definition für die Natürlichkeit bei Sortierverfahren.
Also z.B. die Folge 3 10 14 19 5 7 1, die ich durch ein Sortierverfahren gewinne (nicht das Endergebnis), wäre meiner Meinung nach natürlich, weil ja eine gewisse Vorsortierung vorliegt.
Vielen Dank für Eure Hilfe
Mit freundlichem Gruß
Ralf
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 13:18 Mi 01.08.2007 | | Autor: | Mumrel |
Hi RalU
Also meines Wissens ist die Natürlichkiet eines Sortierverfahrens synonym zur Ordnungsverträglichkeit und bedeutet im Klartext:
Ein Sortierverfahren heißt natürlich/ordnungsverträglich, wenn es auf Daten die schon eine gewisse Vorsortieung besitzten schneller arbeitet, als auf völlig unsortierten.
Das Maß der Vorsortierung ist der Fehlstand, genau definieren kann ich das gerade nicht, aber ich glaube es ist die minimale Anzahl an Vertauschungen die notwenig sind um aus den Daten eine sortierte Folge zu machen.
Der Algo muss also Daten mit kleinerem Fehlstand stets schneller wie Daten mit großem Fehlstand sortieren, dann heißt das Verfahren (!) natürlich.
Natürlich wohl, weil der Mensch für eine Folge bei der nur zwei Elemente in der falschen Reihenfolge vorliegen, genau nur die beiden vertauscht, natürlich eben ;)
Grüße Murmel
|
|
|
|
