Re: Wie logisch richtig sortieren: 1,2,3,21 (nicht 1,2,21,3)
Hi,
dachte eigentlich topologisches Sortieren besagt nur, dass nicht alle Elemente Paarweise vergleichbar sind. Also nimmt man "zufällig" ein Element und sortiert alle Elemente, die sich mit diesem Vergleichen lassen. Nun schaut man sich die Menge der unbetrachteten Elemente an und geht wieder so vor, zum Schluß erhält man also eine Sortierung, dass für jede Teilmenge von paarweise vergleichbaren Elementen sortiert ist, doch die Reihenfolge dieser Teilmengen wäre dann beliebig. Aber klar, kenne ich auch am ehesten im Zusammenhang mit Graphen und kann es auch noch falsch in Erinnerung haben (begegnet mir eher selten als Begriff). Was Merge- und Quicksort angeht, so sollte man wirklich nicht vergessen, dass die Asymptotische Laufzeit konstante Faktoren versteckt (sonst stellt sich schnell die Frage warum Quicksort und nicht Bubblesort, beide O(n^{2})), aber umsonst heißt der Quicksort nicht Quicksort. Amortisiert komme ich ja auch nur auf O(n*log n), aber was wichtiger ist, wie alzmair schon sagte, ich muss immer die ganze Menge im Speicher halten. Also welche Sortierung die schnellste ist (immerhin auch in linearer Zeit möglich), hängt doch stark von der Menge der Daten und der Art des Speichers ab, sollte hier aber nicht das Problem sein. |
Re: Wie logisch richtig sortieren: 1,2,3,21 (nicht 1,2,21,3)
Zitat:
Zitat:
Ich gehe nur davon aus, daß eben das stabile Sortierverfahren gemeint war. Bei stabilen Sortierverfahren ist sicher, daß bei Übereinstimmen zweier Elemente (nach dem jeweiligen Sortierkriterium) die bisherige Sortierung beibehalten wird. Das ist bei instabilen Verfahren, wie zB QuickSort nicht zwingend der Fall. Bsp:
Code:
Wir sortieren erstmal nach den Zahlen:
10-a
13-g 17-c 14-c 21-r 11-u 13-h
Code:
Dann nach den Buchstaben
10-a
11-u 13-g 13-h 14-c 17-c 21-r
Code:
Es ist jetzt hier gewährleistet, daß gleiche Zahlen nach dem 2. Sortieren auch immer noch jeweils richtig nach Buchstaben sortiert sind.
10-a
14-c 17-c 13-g // g und h sind bei 13 in der 13-h // richtigen Reihenfolge 21-r 11-u PS: Ich hätte vielleicht ein aussagekräftigeres und besseres Beispiel wählen können, aber ich hab keine Lust dazu gehabt :stupid: Hoffe, das is trotzdem halbwegs klar geworden, sonst frag nochmal. ;) |
Re: Wie logisch richtig sortieren: 1,2,3,21 (nicht 1,2,21,3)
Hallo,
hier findet sich eine Funktion, die die "Natürliche Sortierung" (so heisst das Ganze) unterstützt. Funktioniert genauso wir CompareString o. ä. Gruß xaromz |
Re: Wie logisch richtig sortieren: 1,2,3,21 (nicht 1,2,21,3)
@leddl: Mein Vorschlag basiert auf einer totalen Ordnung und sortiert nur ein Mal, sodass der Unterschied zwischen 'stabilen' und 'instabilen'Sortierverfahren obsolet ist. Oder anders herum: Jedes Sortierverfahren wird bei einer totalen Ordnungsfunktion immer korrekt und 'stabil' sein, weil eben die Elemente immer eine eindeutige Reihenfolge haben.
Deshalb mein Vorschlag, eine totale Ordnung auf die Titelliste über die Vergleichsfunktion abzubilden und dann ein X-beliebiges Sortierverfahren zu verwenden. |
Re: Wie logisch richtig sortieren: 1,2,3,21 (nicht 1,2,21,3)
Zitat:
http://www.delphipraxis.net/internal...t.php?p=250797 das passende gefunden. Danke an alle. |
Re: Wie logisch richtig sortieren: 1,2,3,21 (nicht 1,2,21,3)
Du könntest ja auch den String in ein Array splitten, wobei der Übergang Zahl-Sonstiges (ausser . und , ) und Sonstiges-Zahl jeweils ein neues Array eröffnet:
Aus 'Bitmap2Icon12345.exe' wird ['Bitmap','2','Icon','12345','.exe']. Das musst du dann nur noch nacheinander sortieren, wobei du, wenn es mit inttostr funktioniert, die Zahlenwerte vergleichst. |
Re: Wie logisch richtig sortieren: 1,2,3,21 (nicht 1,2,21,3)
Was heißt nacheinander sortieren?
Sortiere ich nach der ersten Spalte, dann wird nach der ersten Spalte sortiert. Wie kann ich denn der 2. Spalte sagen, dass sie nur innerhalb der gleichen der 1. Spalte sortieren soll? Soll ich die 1. Spalte abgehen und dann nur die Teile, in denen die jeweilige Zeile den nachfolgenden Zeilen gleich ist, einem Sortieralgortihmus unterwerfen? Oder gibts da einfachere Möglichkeiten? |
Re: Wie logisch richtig sortieren: 1,2,3,21 (nicht 1,2,21,3)
Zitat:
Delphi-Quellcode:
//****************************************************************************//
function NatCompareText(const S1, S2: WideString): Integer; begin SetLastError(0); Result := CompareStringW(LOCALE_USER_DEFAULT, NORM_IGNORECASE or NORM_IGNORENONSPACE or NORM_IGNORESYMBOLS, PWideChar(S1), Length(S1), PWideChar(S2), Length(S2)) - 2; case GetLastError of 0: ; ERROR_CALL_NOT_IMPLEMENTED: Result := DumbItDownFor95(S1, S2, NORM_IGNORECASE or NORM_IGNORENONSPACE or NORM_IGNORESYMBOLS); else RaiseLastOSError; end; end; //****************************************************************************// //****************************************************************************// //Und falls es doch Probleme gibt (wurde im PSDK extra drauf hingewiesen): function DumbItDownFor95(const S1, S2: WideString; CmpFlags: Integer): Integer; var a1, a2: AnsiString; begin a1 := s1; a2 := s2; Result := CompareStringA(LOCALE_USER_DEFAULT, CmpFlags, PChar(a1), Length(a1), PChar(a2), Length(a2)) - 2; end; Nur leider funktioniert sie überhaupt nicht. Sie bewertet immer noch '2' größer als '14'. |
Re: Wie logisch richtig sortieren: 1,2,3,21 (nicht 1,2,21,3)
Ich verweise nochmal auf meinen Beitrag auf der vorigen Seite, in dem ich genau erklärt habe, wie man das anstellen kann, so dass es garantiert funktioniert. Kein Windows kann wissen, wie deine Titel strukturiert sind, das weisst nur Du. Also musst Du die Titel auseinanderpflücken und getrennt sortieren. So schwer ist das doch nicht. Außer, die Title sind immer wieder anders sortiert, aber dann kann auch der beste Rechner Nichts ausrichten...
Und wenn Du willst, dass '2' kleiner sein soll, also '14', dann versuchs mal mit 'StrToInt' o.ä. |
Re: Wie logisch richtig sortieren: 1,2,3,21 (nicht 1,2,21,3)
Zitat:
Vor allem, wenn man einen geschickten randomisierten Quicksort verwendet erhält man nachweislich nie den Worst-Case. Will heissen wir ziehen hier zum Vergleich sowieso immer nur den Average-Case heran und der ist beim Quicksort mit O(n*log(n)) nunmal nachweislich am Optimum. Deswegen heisst das Ding ja auch quicksort: Weil es der schnellste zur Zeit bekannte Sortieralgorithmus ist. |
Alle Zeitangaben in WEZ +1. Es ist jetzt 11:02 Uhr. |
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz