AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren

Array sortieren und durchsuchen

Ein Thema von roboter202 · begonnen am 7. Okt 2011 · letzter Beitrag vom 8. Okt 2011
Antwort Antwort
roboter202

Registriert seit: 6. Mär 2011
98 Beiträge
 
Delphi 6 Professional
 
#1

Array sortieren und durchsuchen

  Alt 7. Okt 2011, 23:45
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
Christian
i := 0 ; While i = 0 do beep ;
  Mit Zitat antworten Zitat
Delphi-Laie

Registriert seit: 25. Nov 2005
1.474 Beiträge
 
Delphi 10.1 Berlin Starter
 
#2

AW: Array sortieren und durchsuchen

  Alt 7. Okt 2011, 23:57
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.

Und dass immer weiter wiederholen bis es nur noch 2 Elemente gibt.
2? Oder doch nur noch eines, das gesuchte Zielelement?

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.

Geändert von Delphi-Laie ( 8. Okt 2011 um 11:20 Uhr)
  Mit Zitat antworten Zitat
FredlFesl

Registriert seit: 19. Apr 2011
293 Beiträge
 
Delphi 2009 Enterprise
 
#3

AW: Array sortieren und durchsuchen

  Alt 8. Okt 2011, 10:07
Na ja, die schnellste ist es nicht. Hashmaps sind noch schneller.
Das Bild hängt schief.
  Mit Zitat antworten Zitat
roboter202

Registriert seit: 6. Mär 2011
98 Beiträge
 
Delphi 6 Professional
 
#4

AW: Array sortieren und durchsuchen

  Alt 8. Okt 2011, 12:40
[QUOTE=Delphi-Laie;1129246]
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/
Christian
i := 0 ; While i = 0 do beep ;

Geändert von roboter202 ( 8. Okt 2011 um 12:44 Uhr) Grund: Problem gelöst
  Mit Zitat antworten Zitat
Delphi-Laie

Registriert seit: 25. Nov 2005
1.474 Beiträge
 
Delphi 10.1 Berlin Starter
 
#5

AW: Array sortieren und durchsuchen

  Alt 8. Okt 2011, 13:26
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

Geändert von Delphi-Laie ( 8. Okt 2011 um 13:29 Uhr)
  Mit Zitat antworten Zitat
Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 01:59 Uhr.
Powered by vBulletin® Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2021 by Daniel R. Wolf