Spezielle Form der Array Sortierung

xenilio · Hält's aus hier Beiträge: 4

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:

markieren

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:

markieren

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:

markieren

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:

markieren

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:

markieren

Quelltext

1:
2:
3:

B[1] = 1
B[2] = 2
B[3] = 3

oder meinetwegen auch

markieren

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 · Verfasst: 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 · Hält's aus hier Beiträge: 4

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):

markieren

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 · Verfasst: 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 · Hält's aus hier Beiträge: 4

Hier ist nun die redigierte Version:

markieren

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
  // Schon_Vorgekommen mit Nullen initialisieren
  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:

markieren

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:

markieren

Delphi-Quelltext

1:	TemporaryArray := GetTheKeys(LetterRateDe);

Trotzdem liefert

markieren

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 · Verfasst: 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

. Nimm also analog zu deinem TIntArray lieber ein TRealArray als Parameter.

_________________
>λ=

xenilio · Hält's aus hier Beiträge: 4

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!

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme