Array sortieren und durchsuchen

[roboter202]

Hallo,

Ich hab einen Array

arContent : array of TNode; (TNode ist ein Klasse.)

Ich möchte diesen Array anhand eines Parameters dF: Double; der Klasse TNode sortieren. Und auch dadurch schnell durchsuchen können.

Konkret muss ich folgende Operationen ausführen:

- Ich muss einen speziellen Eintrag finden für den ich F kenne.
- Beim Einfügen muss ich ein Objekt (TNode) anhand eines f Wertes einsortieren.
- Und ich muss überprüfen ob ein Objekt (TNode) sich bereits im Array befindet.

Wie durchsucht man nun so einen Array?!

Ich würde vermutlich in der Mitte anfangen und wenn der Wert zu groß ist in der Mitte der Unteren Hälfte anfangen. Und dass immer weiter wiederholen bis es nur noch 2 Elemente gibt. Und dann würde ich die Elemente einzeln durchlaufen.

Soweit die Idee. Aber ich habe keine Vorstellung davon wie ich das umsetzten soll.

Gruß roboter202

[Delphi-Laie]

Zitat von roboter202:

Wie durchsucht man nun so einen Array?!

Ich würde vermutlich in der Mitte anfangen und wenn der Wert zu groß ist in der Mitte der Unteren Hälfte anfangen.

Usw. usf., nicht wahr? Das nennt sich binäre Suche und ist evtl. die schnellste Suchmethode. Voraussetzung ist jedoch, daß die Elemente im Array sortiert vorliegen, sonst taugt nur die einfache lineare Suche, die quälend langsam sein/werden kann. Die Reihenfolge Sortieren - Suchen nennst Du ja auch so korrekterweise im Thema der Diskussion. Zum Sortieren gibt es eine Unzahl Sortieralgorithmen mit verschiedenen Leistungsdaten.

Zitat von roboter202:

Und dass immer weiter wiederholen bis es nur noch 2 Elemente gibt.

2? Oder doch nur noch eines, das gesuchte Zielelement?

Zitat von roboter202:

Und dann würde ich die Elemente einzeln durchlaufen.

Wie jetzt, die Knoten? Du sortierst/suchst die Elemente (Knoten) doch anhand ihrer Schlüsselelemente (das sind die, die beim Suchen/Sortieren relant sind, also abgefragt und verglichen werden). Oder meinst Du, daß Du das Array elementeweise durchläufst? Das passiert bei der binären Suche ja genau nicht, denn dort wird über verschiedene Distanzen gesprungen.

[FredlFesl]

Na ja, die schnellste ist es nicht. Hashmaps sind noch schneller.

[roboter202]

[QUOTE=Delphi-Laie;1129246]

Zitat von roboter202:

Zitat von roboter202:

Und dann würde ich die Elemente einzeln durchlaufen.

Wie jetzt, die Knoten? Du sortierst/suchst die Elemente (Knoten) doch anhand ihrer Schlüsselelemente (das sind die, die beim Suchen/Sortieren relant sind, also abgefragt und verglichen werden). Oder meinst Du, daß Du das Array elementeweise durchläufst? Das passiert bei der binären Suche ja genau nicht, denn dort wird über verschiedene Distanzen gesprungen.

Nein, Nur wenn es noch 2 Elemente gibt.

Also. Wie es scheint hast du verstanden was ich möchte. Ich hab nur keinen Plan wie ich die Schleife, die immer die hälfte halbiert aufbauen soll.

Zum Sortieren.

Ich werde die Elemente mit einer Funktion einreihen. dazu wollte ich auch hier erst nach dem f Wert suchen und dann den Eintrag dazwischen schieben.

PROBLEM hat sich gerade GELÖST

http://www.delphi-treff.de/tipps/alg...binaere-suche/

[Delphi-Laie]

Und ich wollte Dir gerade einen Lösungsweg mit einer m.E. etwas eleganteren while-Schleife aufzeigen.

Also, so ungefähr:

Delphi-Quellcode:

while untere_Grenze<obere_Grenze do 
  begin
  Mitte:=(obere_Grenze-untere_Grenze) div 2
  if //hier die Prüfung des gesuchten Elemente(schlüssel)s mit dem Elemente(schlüssel) an der Position Mitte und davon abhänig:
  then obere_Grenze:=Mitte
  else untere_Grenze:=Mitte
  end