alphabetische Sortierung < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
Hi,
ich komme aus der Mathematik und möchte etwas über das Sortieren herausfinden. Insbesondere interessiert mich die die Realisierung eines alphabetischen Sortieralgorithmuses.
Wenn ich zum Beispiel die Zahlen 1,2,3,4,5,6,7,8,9 vergleich so habe ich einen klaren Ausgang wenn ich zum Beispiel 4 und 5 vergleiche, weiß man sofort, dass 4 kleiner als 5 ist. Habe ich jetzt aber zwei Wörter Zum Beispiel AAAAAB und AAAAAC. Dann stellt sich mir die Frage wie man die beiden vergleicht. Kann man diesen Wörten eventuell einen Index zuordnen, sodass man sofort weiß, dass AAAAAB vor AAAAAC kommt? Also ob man die die Reihenfolge mit einem einzigen Vergleich ermitteln kann oder geht man tatsächlich so vor, dass man zunächst den ersten Buchstaben vergleicht, dann aufgrund der Gleichheit den zweiten Buchstaben, dann den dritten, ..., bis man dann am 6ten Buchstaben erkennt, dass AAAAAB alphabetisch vor AAAAAC steht?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:19 Do 23.10.2014 | | Autor: | DieAcht |
Hallo,
Deine Idee mit den Zahlen kann man realisieren, indem man zum
Beispiel [mm] $A:=0\$, $B:=1\$, \ldots [/mm] setzt. Allerdings wirst man in der Pra-
xis auf andere Methoden stoßen, wie zum Beispiel der direkten
Verwendung von ASCII (Graphen, Bäume, etc. lasse ich außen vor).
Mich verwundert es, dass du ein Mathematikstudent bist und wohl
noch nicht mit "Programmieren" in Verbindung gekommen bist. Das
sollte aber mit Sicherheit bald kommen. Alles andere würde mich
wundern.
Falls dich das "Sortieren" interessiert, dann musst du zwischen
vergleichsbasiertem Sortieren und nicht-vergleichsbasiertes Sor-
tieren unterscheiden. Ich empfehle allerdings mit ersterem an-
zufangen. Auf Wikipedia findest du sicher eine Liste aller üb-
lichen Sortierverfahren. Vielleicht probierst du aber zunächst
selbst zum Beispiel eine vorgegebene Liste, zum Beispiel
[mm] A:=\{7,-5,100,2\},
[/mm]
mit einer Sprache deiner Wahl zu sortieren. Die Schwierigkeit
wird ziemlich schnell wachsen, aber das wirst du mit Sicher-
heit schnell selbst herausfinden.
Gruß
DieAcht
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:54 Fr 24.10.2014 | | Autor: | felixf |
Moin,
um die Antwort von DieAcht etwas zu ergänzen:
> Habe ich jetzt aber zwei Wörter Zum
> Beispiel AAAAAB und AAAAAC. Dann stellt sich mir die Frage
> wie man die beiden vergleicht. Kann man diesen Wörten
> eventuell einen Index zuordnen, sodass man sofort weiß,
> dass AAAAAB vor AAAAAC kommt? Also ob man die die
> Reihenfolge mit einem einzigen Vergleich ermitteln kann
> oder geht man tatsächlich so vor, dass man zunächst den
> ersten Buchstaben vergleicht, dann aufgrund der Gleichheit
> den zweiten Buchstaben, dann den dritten, ..., bis man dann
> am 6ten Buchstaben erkennt, dass AAAAAB alphabetisch vor
> AAAAAC steht?
Normalerweise verwendet man für Wörter die sogenannte ![[]](/images/popup.gif) lexikographische Ordnung. (Das ist in etwa das, was du oben beschreibst.) Diese heisst so, weil sie Wörter "wie im Lexikon" sortiert. Einen Index ordnet sie allerdings nicht zu. (Das geht gar nicht, sobald es mehr als einen Buchstaben gibt; siehe ganz unten.)
Dass man allen endlichen Buchstabenketten einen Index zuordnen kann folgt daraus dass die Menge dieser abzählbar ist. Das ist die mathematische Antwort 
Eine konkrete Aufzählung anzugeben ist schon schwieriger. Wenn du $n$ Buchstaben hast, gibt es [mm] $n^k$ [/mm] Wörter mit genau $k$ Buchstaben. Wenn du $k$ festhälst, kannst du das Wort mit den Buchstaben [mm] $i_1, \dots, i_k$ [/mm] (wobei [mm] $i_j [/mm] = 0$ fuer den ersten Buchstaben, [mm] $i_j [/mm] = 1$ fuer den zweiten, ..., [mm] $i_j [/mm] = n-1$ fuer den $n$-ten Buchstaben sei) den Index [mm] $I(i_1, \dots, i_k) [/mm] := [mm] \sum_{j=1}^k i_j n^{j-1}$ [/mm] zuordnen; dies ist eine Zahl zwischen $0$ und [mm] $n^k [/mm] - 1$. Der Fall $n = 10$ sollte dir definitiv bekannt vorkommen.
Aus der mathematischen Sicht her kann man nun recht einfach Indices bestimmen, so dass ein Wort mit $k$ Buchstaben vor einem Wort mit [mm] $\ell$ [/mm] Buchstaben kommt, falls $k < [mm] \ell$ [/mm] ist. Die Indizes $0$ bis [mm] $n^0 [/mm] - 1$ beschreiben Woerter der Laenge 0, die Indices [mm] $n^0$ [/mm] bis [mm] $n^0 [/mm] + [mm] n^1 [/mm] - 1$ Woerter der Laenge 1, die Indices [mm] $n^0 [/mm] + [mm] n^1$ [/mm] bis [mm] $n^0 [/mm] + [mm] n^1 [/mm] + [mm] n^2 [/mm] - 1$ Woerter der Laenge 2, etc.
Ich vermute allerdings, dass du alle Woerter, die mit $A$ anfangen, vor allen Woertern, die mit $B$ anfangen, haben willst. Da es aber unendlich viele Woerter gibt, die mit $A$ anfangen, ist es nicht moeglich hier Indices zu verteilen, so dass alle Woerter, die mit $A$ anfangen, vor allen Woertern kommen, die mit $B$ anfangen. Wenn man nur einen Buchstaben hat, sagen wir $A$, dann geht das wieder: die Laenge des Wortes ist gerade der Index.
LG Felix
|
|
|
|
