Entwickler-Ecke
Delphi Language (Object-Pascal) / CLX - Spezielle Form der Array Sortierung
xenilio - So 07.06.09 11:48
Titel: Spezielle Form der Array Sortierung
Hallo zusammen,
ich steh gerade etwas auf dem Schlauch. Arbeite schon seit Stunden an einem Kryptoanalysetool in Delphi und habe gerade eine Problemstellung, für die ich keine Lösung finde.
Ich habe ein Array A, das Kommawerte enthält:
Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
| A[1] = 0.7
A[2] = 1.3
A[3] = 7.8
A[4] = 4.4
A[5] = 2.7
A[6] = 3.9
A[7] = 1.7
A[8] = 9.6
A[9] = 3.3 |
Nun möchte ich ein Array B erstellen, das ebenfalls die Schlüssel 1 bis 9 hat und als Werte die Schlüssel aus Array A, nach folgendem Schema: B[1] soll den Schlüssel K mit dem höchsten A[K] enthalten, B[9] den Schlüssel K mit dem niedrigsten A[K].
Das sähe dann anhand des obigen Beispiels folgendermaßen aus:
Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
| B[1] = 8
B[2] = 3
B[3] = 4
B[4] = 6
B[5] = 9
B[6] = 5
B[7] = 7
B[8] = 2
B[9] = 1 |
Meine Idee war, ein temporäres Array T zu erstellen, das zunächst mit den gleichen Schlüsseln und Werten wie A gefüllt und dann mit BubbleSort absteigend sortiert wird (die ursprünglichen Schlüssel entfallen).
Dann wiederum eine Schleife:
Quelltext
1:
2:
3:
4:
5:
6:
| i := 1;
while i <= 9 do
begin
B[i] := getKeyByValue(A, T[i]);
inc(i);
end; |
getKeyByValue ist eine eigene Funktion und liefert in diesem Fall aus dem Array A den Schlüssel K mit A[K] = T[i] zurück.
Das funktioniert prinzipiell sogar, allerdings nur solange im Array A keine Werte doppelt auftreten:
Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
| Aus
A[1] = 0.7
A[2] = 0.5
A[3] = 0.5
wird
B[1] = 1
B[2] = 3
B[3] = 3 |
Ich brauche es aber so, dass alle Schlüssel zurückgeliefert werden, auch bei gleichen Werten:
Quelltext
1:
2:
3:
| B[1] = 1
B[2] = 2
B[3] = 3 |
oder meinetwegen auch
Quelltext
1:
2:
3:
| B[1] = 1
B[2] = 3
B[3] = 2 |
Die Reihenfolge spielt dabei keine Rolle. Es müssen nur alle Schlüssel des Arrays einmal auftauchen. Wie setze ich das am besten um?
Vielen Dank im Voraus!
xenilio
jaenicke - So 07.06.09 13:22
Lösch doch mit GetKeyByValue den Wert einfach, dann kann der Wert an dem ersten Index nicht mehr gefunden werden. ;-)
xenilio - So 07.06.09 13:32
Okay, das behalte ich im Hinterkopf.
Ich hab mir aber jetzt ne Funktion gebastelt, die das etwas eleganter löst:
GetTheKeys liefert ein Array zurück, das besagte Schlüssel enthält. TIntArray ist ein Array[1..26] of Integer (Ja, es sind in Wirklichkeit 26 Werte und nicht 9):
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
| function TFUncrypt.GetTheKeys(A: Array of Real) : TIntArray;
var i,j,n,highest_key : integer;
highest_value: real;
B: TIntArray;
Temp: Array[1..26] of Integer;
begin
n := length(A);
for i:=1 to n do
begin
highest_key := 0;
highest_value := 0;
for j:=1 to n do
begin
if (highest_value < A[j]) AND (Temp[j] <> 1) then
begin
highest_key := j;
highest_value := A[j];
end;
end;
B[i] := highest_key + 1;
Temp[highest_key] := 1;
end;
GetTheKeys := B;
end; |
.
Merkwürdigerweise fehlt hier hinterher eine 1 in B, die ja auf A[1] hinweist, während alle Werte danach dementsprechend eine Stelle zu früh kommen und der 26. Wert (da nicht gesetzt) irgendeine merkwürdige, sehr hohe Zahl ist. Kann mir das einer erklären? Es kommt mir so vor, als würde i einen Sprung machen, wenn highest_key auf 1 kommt. Aber dem ist ja nicht so.
xenilio
Moderiert von 
Kha: Code- durch Delphi-Tags ersetzt
Kha - So 07.06.09 13:39
Du musst Temp (toller Name ;) ) noch mit Nullen initialisieren. Das highest_key + 1 verstehe ich allerdings nicht :nixweiss: .
Es gäbe auch noch Lösungen in O(n * log n), aber für 26 Werte wahrscheinlich nicht so interessant ;) .
xenilio - So 07.06.09 14:36
Hier ist nun die redigierte Version:
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
| function TFUncrypt.GetTheKeys(A: Array of Real) : TIntArray;
var i,j,n,highest_key : integer;
highest_value: real;
B: TIntArray;
Schon_Vorgekommen: Array[1..26] of Integer;
begin
for i:=1 to 26 do
begin
Schon_Vorgekommen[i] := 0;
end;
n := 26;
for i:=1 to n do
begin
highest_key := 0;
highest_value := 0;
for j:=1 to n do
begin
if (highest_value < A[j]) AND (Schon_Vorgekommen[j] <> 1) then
begin
highest_key := j;
highest_value := A[j];
end;
end;
B[i] := highest_key;
Schon_Vorgekommen[highest_key] := 1;
end;
GetTheKeys := B;
end; |
Das hier ist das Array:
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
| LetterRateDe[1] := 0.0651;
LetterRateDe[2]:= 0.0189;
LetterRateDe[3] := 0.0306;
LetterRateDe[4] := 0.0508;
LetterRateDe[5] := 0.1740;
LetterRateDe[6] := 0.0166;
LetterRateDe[7] := 0.0301;
LetterRateDe[8] := 0.0476;
LetterRateDe[9] := 0.0755;
LetterRateDe[10] := 0.0027;
LetterRateDe[11] := 0.0121;
LetterRateDe[12] := 0.0344;
LetterRateDe[13] := 0.0253;
LetterRateDe[14] := 0.0978;
LetterRateDe[15] := 0.0251;
LetterRateDe[16] := 0.0079;
LetterRateDe[17] := 0.002;
LetterRateDe[18] := 0.0700;
LetterRateDe[19] := 0.0727;
LetterRateDe[20] := 0.0615;
LetterRateDe[21] := 0.0435;
LetterRateDe[22] := 0.067;
LetterRateDe[23] := 0.0188;
LetterRateDe[24] := 0.0003;
LetterRateDe[25] := 0.0004;
LetterRateDe[26] := 0.0113; |
Der Aufruf der Funktion sieht so aus:
Delphi-Quelltext
1:
| TemporaryArray := GetTheKeys(LetterRateDe); |
Trotzdem liefert
Delphi-Quelltext
1:
2:
3:
4:
| for i := 1 to 26 do
begin
showMessage(IntToStr(i) + ': ' + IntToStr(TemporaryArray[i]));
end; |
als erste Zahl nicht die 5, sondern die 4, und als letzte Zahl die 26 statt der 24. Die Zahlen dazwischen habe ich im Einzelnen noch nicht überprüft.
Ich verstehe das nicht. Vom Prinzip her müsste das doch so klappen oder?
Moderiert von Narses: Code- durch Delphi-Tags ersetzt
Kha - So 07.06.09 16:08
Vom Prinzip ja, also würde ich als nächsten Schritt mal den Debugger einschalten: Der verrät mir, dass A als offener Array-Parameter natürlich 0-indiziert ist, ups :D . Nimm also analog zu deinem TIntArray lieber ein TRealArray als Parameter.
xenilio - So 07.06.09 16:25
:D Vielen Dank! Ich hatte mir schon gedacht, dass es irgendwas mit falscher Indizierung oder Adressierung zu tun hat. Allerdings reichen meine Delphi Kenntnisse nicht so weit. Danke!
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2026 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!