Quicksort: Nur Nullen

[Rumnic]

Hallo, mein erster Post hier und ich komme mal gleich zur Sache :spin:

Ich brauche ein Programm, welches einen sortierten Array durch binäres Suchen nach der gewünschten Zahl durchsuchen soll. Soweit bin ich aber noch garnicht gekommen, weil mein Quicksort nur Nullen ausgibt oder ich einen anderen blöden Fehler drin habe, den ich einfach nicht finde. Dazu soll gesagt sein, dass ich noch nicht lange am Programmieren bin und mein Informathik-Lehrer ziemlich flott vorran geht ^^.

Der Quicksort stammt aus einem Programm eines Mitschülers, in dessen Programm er wunderbar funktioniert, bei mir will er das jedoch nicht.

Delphi-Quellcode:

procedure quicksort(var arr : tZahlen; lo, hi : word);
procedure partition(var arr : tZahlen; lo, hi : word; var l, r : integer);

var pivot, temp: word;
begin
  l := lo;
  r := hi;
  pivot := arr[lo];
  while l < r do
  begin
    if arr[r] > pivot then
      r := r-1
    else if arr[l] <= pivot then
      l := l+1
    else
      begin
          temp := arr[l];
          arr[l] := arr[r];
          arr[r] := temp;
      end;
  end;

  arr[lo]:= arr[r];
  arr[r] := pivot;
  dec(r);
  inc(l);

end;

var l ,r : integer;

begin
  partition(arr, lo, hi, l, r);
  if lo<r then quicksort(arr, lo,r);
  if l<hi then quicksort(arr, l,hi);
end;

Das ist mein Quicksort und jetzt noch das Schreiben in den Array:

Delphi-Quellcode:

procedure TForm1.btSortClick(Sender: TObject);
var i, eingabe : word;
begin
  memSort.lines.clear;
  eingabe := strtoint(edEingabe.Text);
  quicksort(arrZahlen2, low(arrZahlen2), high(arrZahlen2));
  for i := 1 to eingabe do
    memSort.lines.add(inttostr(arrZahlen2[i]));
end;

Ich habe ein Feld, in welchem man angeben kann, wie viele Zufallszahlen erzeugt werden sollen, die dann sortiert werden. Kann auch sein, dass ich da einfach einen Fehler im übergeben des Arrays drin habe, aber irgendwie komme ich nicht drauf/übersehe es einfach.

Wäre sehr dankbar, wenn mir jemand auf die Sprünge helfen könnte.



Edit: Hätte noch ein kleines anderes Problem zu einem anderen Thema :mrgreen:
Wie greift man auf den Wert eines Index in einem Array zu, wenn dieser Index aus mehreren Elementen besteht. Z.B. haben wir eine Telefonliste mit Nachname, Vorname und Telefonnummer in einer Zeile im Array und nun sollen wir den Array nach den Nachnamen sortieren. Wie greife ich also nur auf die Nachnamen im Array zu, ohne auch auf Vorname und Telefon zuzugreifen?

[Dunkel]

Hallo und willkommen im Forum!

Ist das Dein kompletter Quelltext? Wo füllst Du z.B. arrZahlen2 mit zufälligen Werten?

[Benedikt]

Hallo und herzlich Willkommen in der DP :hi:

Also dein Code funktioniert, hab ihn grade ausprobiert. Was ich mich vielmehr Frage: Wo füllst du den dein Array? Du hast in dem Btn-Click deine Variable eingabe, mit der du ja angeben können willst, wieviele Zufallszahlen erzeugt werden, aber wo schreibst du sie denn dann ins Array rein?

MfG Benedikt

//ups, roter Kasten...

[Rumnic]

Ohje, Ohje, wie blöd. Habe ich einfach ganz vergessen, dass ich den array2 noch nicht gefüllt hab :oops: Danke! :thumb:

[p80286]

Hallo Runnic,

zu Deiner zweiten Frage:
Du hast also einen array of string mit ungefähr folgenden Einträgen

1 Müller, willi 12345
2 Müller, Magdalena 2468
3 Schmitz, Peter 1357

Wenn das so aussieht, dann einfach das Array sortieren, da der Name ja vorne steht.
Willst Du obiges Beispiel nach Vornamen sortieren, dann mußt Du den Vornamen nach vorne kopieren und dann sortieren.
Deine Datensätze sehen dann ungefähr so aus:

1 willi|Müller, willi 12345
2 Magsdalena|Müller, Magdalena 2468
3 Peter|Schmitz, Peter 1357

Das "|" hab ich als Trenner genommen, damit Du einen einfach zu findenden Begrenzer für Deinen Sortierschlüssel hast.

Aber ich würde für solche Daten Records, bzw. TLists verwenden, dann hat mein keine Probleme mit Begrenzern und dem Umkopieren.

Gruß
K-H

[taaktaak]

Moin, Moin.

Zitat:

Aber ich würde für solche Daten Records, bzw. TLists verwenden, dann hat mein keine Probleme mit Begrenzern und dem Umkopieren.

Das kann ich nur bekräftigen! TList ist 'ne viel bessere Möglichkeit mit solchen Daten umzugehen. Also möglichst rechtzeitig damit beschäftigen und gar nicht erst den "falschen" Weg gehen.

[guidok]

Zitat:

Zitat von taaktaak

Moin, Moin.

Zitat:

Aber ich würde für solche Daten Records, bzw. TLists verwenden, dann hat mein keine Probleme mit Begrenzern und dem Umkopieren.

Das kann ich nur bekräftigen! TList ist 'ne viel bessere Möglichkeit mit solchen Daten umzugehen. Also möglichst rechtzeitig damit beschäftigen und gar nicht erst den "falschen" Weg gehen.

Zitat:

Dazu soll gesagt sein, dass ich noch nicht lange am Programmieren bin und mein Informathik-Lehrer ziemlich flott vorran geht ^^.

Es gibt mit Sicherheit geschicktere Wege, aber es handelt sich hier um den Informatikunterricht, da sollte man schon ungefähr den Weg gehen, den der Lehrer vorgibt (es sei denn es ist völliger Quark, was es ja auch geben soll).

[Rumnic]

Zitat:

Zitat von guidok

Zitat:

Zitat von taaktaak

Moin, Moin.

Zitat:

Aber ich würde für solche Daten Records, bzw. TLists verwenden, dann hat mein keine Probleme mit Begrenzern und dem Umkopieren.

Das kann ich nur bekräftigen! TList ist 'ne viel bessere Möglichkeit mit solchen Daten umzugehen. Also möglichst rechtzeitig damit beschäftigen und gar nicht erst den "falschen" Weg gehen.

Zitat:

Dazu soll gesagt sein, dass ich noch nicht lange am Programmieren bin und mein Informathik-Lehrer ziemlich flott vorran geht ^^.

Es gibt mit Sicherheit geschicktere Wege, aber es handelt sich hier um den Informatikunterricht, da sollte man schon ungefähr den Weg gehen, den der Lehrer vorgibt (es sei denn es ist völliger Quark, was es ja auch geben soll).

Wir haben bis jetzt nur mit Arrays gearbeitet. Jetzt kamen noch die Records dazu, von denen unser Lehrer uns einen in ein vorgefertigtes Programm mit den Elementen vName,nName und telefon gesetzt hat und die Aufgabe ist es jetzt, den Array nach Nachnamen und untereinander nach Vornamen zu sortieren. EIne kleine Überlegung haben wir schon angestellt, und zwar, dass man erst nach Vornamen sortieren muss und dann nach Nachnamen.
Der Array[1] sieht dann bsp so aus:
Müller, Lisa, 0123/456789

Es kam noch etwas ganz kurz zur Sprache am Ende der Stunde, was ich aber nicht genau mitbekommen habe. Das waar glaube ich so etwas wie : array[i].vName, um beim index i im Array nur auf den Vornamen zuzugreifen. Ich habe das dann in meinem Programm kurz ausprobiert, indem ich dem Quicksort nicht array sondern array.vName übergeben wollte. Das wurde mir allerdings rot unterstrichelt: "tArrEintrag enthält kein Element namen vName"

Delphi-Quellcode:

procedure TFormTelefon.Button2Click(Sender: TObject);
var i : word;
begin
  sortiere(arrEintrag.vName, low(arrEintrag), high(arrEintrag));      //warum??
  for i := 1 to high(arrEintrag) do
    memArray.lines.add(arrEintrag[i]);
end;

In der Obenflächenunit:

Delphi-Quellcode:

implementation

{$R *.dfm}

uses uStore,   uSort ;

var arrEintrag : tArrEintrag;  // <---

in uSort:

Delphi-Quellcode:

type tArrEintrag = array[1..100] of tEintrag;

in uStore:

Delphi-Quellcode:

  tEintrag = record
              vName: tVName;
              nName: tNName;
              telefon: tTelefon;
            end;

Ich verstehe das jetzt als eine funktionierende "Kette".
arrEintrag ist als tArrEintrag definiert, tArrEintrag mit tEintrag und in tEintrag steht vName?! :wiejetzt:

[guidok]

Zitat:

EIne kleine Überlegung haben wir schon angestellt, und zwar, dass man erst nach Vornamen sortieren muss und dann nach Nachnamen.

Also ich würde nach Nach- und Vornamen gleichzeitig sortieren, einfach indem ich zum Sortieren die Felder nName und vName addiere.

Dann sortierst du z.B. nach "MüllerLisa" und damit hast du Nach- und Vorname in einem Rutsch richtig sortiert. Zur Darstellung nimmst du die Felde dann wieder einzeln her.

[guidok]

Zitat:

Es kam noch etwas ganz kurz zur Sprache am Ende der Stunde, was ich aber nicht genau mitbekommen habe. Das waar glaube ich so etwas wie : array[i].vName, um beim index i im Array nur auf den Vornamen zuzugreifen. Ich habe das dann in meinem Programm kurz ausprobiert, indem ich dem Quicksort nicht array sondern array.vName übergeben wollte. Das wurde mir allerdings rot unterstrichelt: "tArrEintrag enthält kein Element namen vName"

Delphi-Quellcode:

arrEintrag[i].vName

Das sollte schon so funktionieren...