| Vorheriges Thema anzeigen :: Nächstes Thema anzeigen |
| Autor |
Nachricht |
St_W
Anmeldungsdatum: 22.07.2007
Beiträge: 956
Wohnort: Austria
|
 Verfasst am: 15.06.2008, 13:40 Titel: Sortieralgorithmen |
 |
|
Hallo!
Für ein Unterprogramm, dass einen Datei-Auswählen-Dialog anzeigt benötige ich einen Algorithmus, um die Dateinamen dem Namen nach zu sortieren (wie z.B. im MS-DOS Editor oder in der QB-IDE selbst). Dieser sollte sehr schnell und - wenn möglich - nicht speicherintensiv oder schwer umsetzbar sein.
Könnt ihr mir da einen Algorithmus von den vielen Sortieralgorithmen empfehlen?
LG und Vielen Dank im Voraus,
St_W
_________________
Aktuelle FreeBasic Builds, Projekte, Code-Snippets unter http://users.freebasic-portal.de/stw/
http://www.mv-lacken.at Musikverein Lacken (MV Lacken) |
|
| Nach oben |
|
 |
Sebastian
Administrator
Anmeldungsdatum: 10.09.2004
Beiträge: 5969
Wohnort: Deutschland
|
|
| Nach oben |
|
|
Jojo
alter Rang
Anmeldungsdatum: 12.02.2005
Beiträge: 9736
Wohnort: Neben der Festplatte
|
| Verfasst am: 15.06.2008, 15:10 Titel: |
|
|
ein beispielcode für den von sebastian genannten quicksort-algorithmus:
| Code: |
SUB QuickSort (Zeile() AS STRING, Anzahl AS INTEGER)
CONST MaxMerk = 15 ' reicht zum Sortieren von
' 2^15 Elementen
DIM Links AS INTEGER, Rechts AS INTEGER
DIM MerkAnzahl AS INTEGER, Vergleich AS STRING
DIM MerkL(1 TO MaxMerk) AS INTEGER
DIM MerkR(1 TO MaxMerk) AS INTEGER
MerkAnzahl = 1
MerkL(1) = 1
MerkR(1) = Anzahl
DO
Links = MerkL(MerkAnzahl): Rechts = MerkR(MerkAnzahl)
MerkAnzahl = MerkAnzahl - 1
DO
i% = Links: j% = Rechts
Vergleich = Zeile((Links + Rechts) \ 2)
DO
DO WHILE Zeile(i%) < Vergleich: i% = i% + 1: LOOP
DO WHILE Vergleich < Zeile(j%): j% = j% - 1: LOOP
IF i% <= j% THEN
SWAP Zeile(i%), Zeile(j%)
i% = i% + 1: j% = j% - 1
END IF
LOOP UNTIL i% > j%
IF j% - Links < Rechts - i% THEN
IF i% < Rechts THEN
MerkAnzahl = MerkAnzahl + 1
MerkL(MerkAnzahl) = i%
MerkR(MerkAnzahl) = Rechts
END IF
Rechts = j%
ELSE
IF Links < j% THEN
MerkAnzahl = MerkAnzahl + 1
MerkL(MerkAnzahl) = Links
MerkR(MerkAnzahl) = j%
END IF
Links = i%
END IF
LOOP WHILE Links < Rechts
LOOP UNTIL MerkAnzahl = 0
END SUB
|
_________________
» Die Mathematik wurde geschaffen, um Probleme zu lösen, die es nicht gäbe, wenn die Mathematik nicht erschaffen worden wäre.
 |
|
| Nach oben |
|
|
MisterD
Anmeldungsdatum: 10.09.2004
Beiträge: 3071
Wohnort: bei Darmstadt
|
| Verfasst am: 15.06.2008, 20:54 Titel: |
|
|
reicht nur im optimalfall zum sortieren von 2^15 elementen, wenn du ne ungünstige konstellation triffst reichts grade mal für 16 elemente ;P
_________________
"It is practically impossible to teach good programming to students that have had a prior exposure to BASIC: as potential programmers they are mentally mutilated beyond hope of regeneration."
Edsger W. Dijkstra |
|
| Nach oben |
|
|
St_W
Anmeldungsdatum: 22.07.2007
Beiträge: 956
Wohnort: Austria
|
| Verfasst am: 17.06.2008, 11:53 Titel: |
|
|
Der Algorithmus funktioniert zwar toll, aber ich verstehe ihn nicht.
Könnte mir das jemand erklären? (den Wikipedia-artikel zu QuickSort habe ich mir übrigens schon durchgelesen)
_________________
Aktuelle FreeBasic Builds, Projekte, Code-Snippets unter http://users.freebasic-portal.de/stw/
http://www.mv-lacken.at Musikverein Lacken (MV Lacken) |
|
| Nach oben |
|
|
MisterD
Anmeldungsdatum: 10.09.2004
Beiträge: 3071
Wohnort: bei Darmstadt
|
| Verfasst am: 17.06.2008, 12:19 Titel: |
|
|
funktioniert nach dem prinzip "nimm dir ne zahl von der du denkst dass sie möglichst nah am mittelwert der sortierenden zahlen liegt, sortiere dann deine liste in zwei gruppen, alle zahlen die größer sind und alle zahlen die kleiner sind als der wert, danach mach das selbe für die beiden neuen listen bis sie jeweils nurnoch 1 element groß sind und schreib sie dann hintereinander" und schon ist das ganze sortiert
_________________
"It is practically impossible to teach good programming to students that have had a prior exposure to BASIC: as potential programmers they are mentally mutilated beyond hope of regeneration."
Edsger W. Dijkstra |
|
| Nach oben |
|
|
Lutz Ifer
Grillmeister
Anmeldungsdatum: 23.09.2005
Beiträge: 555
|
| Verfasst am: 17.06.2008, 16:59 Titel: |
|
|
Lutz Ifer empfiehlt Bogosort 
_________________
Wahnsinn ist nur die Antwort einer gesunden Psyche auf eine kranke Gesellschaft. |
|
| Nach oben |
|
|
b3ast
Anmeldungsdatum: 27.04.2008
Beiträge: 34
|
| Verfasst am: 18.06.2008, 21:47 Titel: |
|
|
| wenn das mit einem zufallsgenerator funktioniert, ist es nicht wirklich zu empfehlen. da wartet man ja unter umständen ne ewigkeit. |
|
| Nach oben |
|
|
Jojo
alter Rang
Anmeldungsdatum: 12.02.2005
Beiträge: 9736
Wohnort: Neben der Festplatte
|
| Verfasst am: 18.06.2008, 22:16 Titel: |
|
|
gratulation, du hast bogosort gerafft! du bist echt spitze! 
_________________
» Die Mathematik wurde geschaffen, um Probleme zu lösen, die es nicht gäbe, wenn die Mathematik nicht erschaffen worden wäre.
|
|
| Nach oben |
|
|
|
FAQ
Suchen
Mitgliederliste
Benutzergruppen
Registrieren
Profil
Einloggen, um private Nachrichten zu lesen
Login
