Such-Algorithmus gesucht

[hoika]

Hallo,

ich stehe hier gerade auf dem Schlauch (wie immer ;) ).
Folgende Daten sind gegeben

Startwert (Datum)
Id (Integer)

etwa so

1.5.2005 35
2.8.2005 32

Die Werte stehen als Klasse in einer List (TList).
Ich suche jetzt nach einem Algorithmus, der mir bei gegebenem Datum die Id ermittelt
also

1.4.2005 -> Fehler
1.5.2005 -> 35
2.5.2005 -> 35
1.8.2005 -> 35
2.8.2005 -> 32
3.8.2005 -> 32 usw.


Kann man das auch über Quicksort machen ?
Ein Expand (also aufrollen der Liste wie 1.5.2005 35, 2.5.2005 35 geht nicht).


Zur Zeit behelfe ich mich mit einer sortierten Liste (nach Startdatum aufwärts)
und Rückwärtssuche, bis ein Eintrag mit Startdatum<=Testdatum gefunden wurde.


Wie sucht man nach solchen Einträgen ?

Danke schon mal im voraus


Heiko

[Der_Unwissende]

Zitat:

Zitat von hoika

Kann man das auch über Quicksort machen ?

Zur Zeit behelfe ich mich mit einer sortierten Liste (nach Startdatum aufwärts)
und Rückwärtssuche, bis ein Eintrag mit Startdatum<=Testdatum gefunden wurde.

Wie sucht man nach solchen Einträgen ?

HI,
ich glaube da ist ein wenig was durcheinander gekommen, was möchtest du denn mit Quicksort machen? Suchen <> Sortieren, Quicksort = Sortieren :wink:
Sortieren kannst du auf jeden Fall per Quicksort, da stellt TList dir eine einfache Möglichkeit zur Verfügung, die eigentlich nur einen Quicksort implementiert. Du musst allerdings sagen, wie verglichen wird (schließlich speicherst du nur Zeiger). Was du machen musst ist einfach eine Methode vom Typ TSortCompare implementieren und an List.Sort übergeben.

Delphi-Quellcode:

TDeinElement = record
  date : TDate;
  value : Integer;
end; 

function compare(Item1, Item2: Pointer): Integer;
begin
  if TDeinElement(Item1).date < TDeinElement(Item1).date then
  begin
    result := 1;
  end

  else if TDeinElement(Item1).date = TDeinElement(Item1).date then
  begin
    result := 0;
  end

  else 
  begin
    result = -1;
  end; 
end;

Na ja, wenn du jetzt ein Element suchst, dann kannst du einfach deine Liste sortieren (die Funktion sort aufrufen und als Argument die Methode compare übergeben). Dann hast du schon mal eine sortierte Liste.
Um jetzt ein Element zu finden kannst du einfach binär suchen. Du nimmst das Element in der Mitte und schaust ob es deinem Datum entspricht oder kleiner bzw. größer ist.
Hast du das Datum gefunden bist du fertig. Ansonsten suchst du rekursiv in dem halben Feld weiter. Irgendwann gibt es nur die Möglichkeit, dass nur noch ein Datum übrig bleibt.

Gruß Der Unwissende

[r2c2]

Verschiedene Sortier-, aber auch Suchalgorithmen gibts hier: www.sortieralgorithmen.de

mfg

Christian

P.S.: BTW: Wenn du sowieso ne Klasse hast, kannst auch ne TObjectList(+ Template) nehmen...

[hoika]

Hallo,

ich meinte Qucksearch.
Die Frage zielte darauf, ob das auch bei dieser Suche geht.

QuickSearch benutze ich schon zur genauen Suche.


Heiko

[r2c2]

Zitat:

Zitat von hoika

ich meinte Qucksearch.
Die Frage zielte darauf, ob das auch bei dieser Suche geht.

Wieso nicht? Für QuickSort bzw. -Search is es nur wichtig, dass es eine eindeutige Reihenfolge gibt...

Zitat:

QuickSearch benutze ich schon zur genauen Suche.

Welche genaue Suche...?

BTW: QuickSearch is auch auf der von mir verlinkten Seite...

mfg

Christian

[hoika]

Hallo,

hm, es klingt einleuchtend.
Mal am Wochenende probieren.


Danke

Heiko