Array sortieren

[Michael S.]

Hallo,
eins vorweg: Ich weiß, dass es eine Suchfunktion gibt und es bereits viele Threads zum Thema Sortieren gibt. Da ich mich aber selber an einem Algorithmus versuchen will, wäre es nett, wenn ihr euch meinen Quelltext mal angucken könntet, da ich bis jetzt auch nach dem lesen verschiedenster anderer Threads keine Lösung gefunden habe. Wie gesagt ich möchte einen Array (MyAdress) ordnen, der von mir erstellte Datentypen (TMyAdress) enthält. Das Ganze soll alphabetisch sortiert werden. Anhaltspunkt soll dabei TMyAdress.Name sein.

Hat nicht wirklich was mit dem Sortieren zu tun, sondern findet lediglich die Anzahl der belegten Array Felder raus:

Delphi-Quellcode:

function Anzahlfinden:integer;
var x:integer;
begin
x:=1;
While MyAdress[x].Name<>'' Do x:=x+1;
Result:=x;
end;

Eigentlicher Sortier Vorgang! Es wird immer das kleinste (zweitkleinste, drittkleinste. usw.) gesucht und mit dem Ersten, Zweiten, Dritten usw. ausgetauscht. ich erhalte keinen Fehler beim Kompilieren, aber er sortiert es einfach nicht richtig:

Delphi-Quellcode:

procedure Arrayordnen;
var Anzahl:integer;
x,y:integer;
min:tmyadress;
minposition:integer;
begin
anzahl:=anzahlfinden;
for y:=1 to (Anzahl-1) Do
    begin
    For x:=y to (Anzahl-1) do
        if MyAdress[x].Name < MyAdress[x+1].Name
        Then
            begin
            Min:= MyAdress[x];
            MinPosition:= x;
            end
        else
            begin
            Min:= MyAdress[x+1];
            minPosition:=x+1;
            end;
    MyAdress[MinPosition]:=MyAdress[y];
    MyAdress[y]:=min;
    end;
end;

Ich programmier noch nicht lange und es wäre nett, wenn ihr mir helfen könntet!
Vielen Dank im Vorraus!

Gruß
Michael

Edit: Hier die Typen und globalen Variablen:
Type:

Delphi-Quellcode:

type
TMyAdress=record
    Name:String;
    Vorname:String;
    Strasse:String;
    PLZ:String;
    Ort:String;
    end;

Globale Variablen:

Delphi-Quellcode:

var
  Form1: TForm1;
  MyAdress:array[1..10] of TMyAdress;
  i:integer =1;

[marabu]

Herzlich willkommen in der Delphi-PRAXiS, Michael.

Kannst du noch die von dir verwendeten Typen und globalen Variablen veröffentlichen?

Freundliche Grüße vom marabu

[Der_Unwissende]

Hi,
ja was du benutzt sieht ein wenig nach dem Bubblesort ohne Optimierung (und imho falsch) aus.

Als ersten und wichtigsten Tipp, solltest du doch deinen Codestil etwas verändern. Zu gutem Stil gehört, dass du immer hierachisch einrückst und dass allen Kontrollstrukturen ein begin end; folgt.

In deinem Fall sähe dass dann so aus

Delphi-Quellcode:

procedure Arrayordnen; 
var Anzahl: integer; 
    x,y: integer; 
    min: tmyadress; 
    minposition: integer; 
begin 
  anzahl:=anzahlfinden; 
  for y:=1 to (Anzahl-1) Do 
    begin 
      For x:=y to (Anzahl-1) do 
        begin
          if MyAdress[x].Name < MyAdress[x+1].Name Then 
            begin 
              Min:= MyAdress[x]; 
              MinPosition:= x; 
            end 
          else 
            begin 
              Min:= MyAdress[x+1]; 
              minPosition:=x+1; 
            end; 
          MyAdress[MinPosition]:=MyAdress[y]; 
          MyAdress[y]:=min; 
        end; // HIER GANZ WICHTIG!
    end; 
end;

Wie du siehst wurde hier ein begin end hinter for x ... eingefügt. Ohne dieses widerholst du zwar die Schleife (Anzahl - 1) - y mal, aber du vergleichst in diesem Durchlauf nur paarweise benachbarte Elemente. Ich denke einfach mal, dass du für jeden dieser Vergleiche auch einmal tauschen möchtest. Andernfalls müsstest du dir das lokale (für y) kleinste Element merken (Ginge dann in Richtung Insertionsort).
Wenn du es so machen wolltest wie ich es jetzt annehme, dann hast du aber eine falsche untere Grenze. In jedem Durchlauf tauscht du so, dass am Ende (der for x Schleife) das größte Element ganz rechts steht. Da du aber die linke Grenze verschiebst, werden die unteren Werte nie sicher sortiert sein. Da solltest du eher die rechte Schranke verschieben.

Sorry, hoffe war jetzt nicht zu schnell dahin geschrieben und du verstehst ein wenig was ich meine. Sonst frag einfach nochmal genauer nach.

Gruß Der Unwissende

[Michael S.]

Erstmal danke für die schnelle Antwort, aber wie du ja schon befürchtet hast, verstehe ich sie nicht ganz...
Wenn beim ersten Durchlauf das kleinste Element gefunden wurde, wird es mit dem an erster Stelle getauscht. Wenn dann beim zweiten Durchlauf das zweitkleinste Element gefunden wurde, wird es mit dem an zweiter Stelle getauscht. Somit braucht das ganze doch nur so viel Durchläufe, wie meine Variable "Anzahl" angibt, oder nicht? Was meinst du dann mit Grenze? Oder meinst du, dass immer mit der letzten, vorletzten usw. getauscht wird???

[Der_Unwissende]

Dein Vergleich ist folgender

Delphi-Quellcode:

 For x:=y to (Anzahl-1) do 
        begin 
          if MyAdress[x].Name < MyAdress[x+1] then
           ....

Du läufst also von links nach rechts. Dein Y wird dabei in jedem Durchlauf größer (und da du von y bis Anzahl - 1 läufst, verschiebst du damit den linken Startindex, das meinte ich als linke Grenze).
Ok, was machst du nun? Du vergleichst das Element an der Stelle x mit dem an x+1. Das heißt, die Elemente die du vergleichst sind immer benachbart.
Hättest du [2,3,7,1] dann würdest du folgende Vergleiche haben: (2,3), (3,7), (7,1). Jetzt das gleiche, mit dem Tauschen wenn der Nachbar (x+1) < x
(2,3) nichts tun
(3,7) nichts tun
(7,1) tauschen
-> [2,3,1,7]
Also ist das größte Element nun an seiner richtigen Stelle. Über das kleinste Element kannst du aber nicht viel sagen. Du gehst aber (fälschlich) davon aus, dass das kleinste Element an der linkesten Stelle steht und betrachtest nur noch den unsortierten Teil, hier also [3,1,7]. Es kann also nicht mehr zu einem korrekten Ergebnis kommen (die 1 wird nie mit der 2 verglichen).

Es gibt halt zwei Ansätze, der eine sieht so aus, wie dass was du schon gesagt hast. Du merkst dir das wirklich kleinte Element und den Index von diesem Element. Dann musst du aber auch alle Elemente mit genau diesem für den Durchlauf kleinsten Element vergleichen und ggf. tauschen. Dann kannst du natürlich davon ausgehen, dass du die linkesten Elemente schon sortiert hast (das entspricht dem Sortieren durch einfügen / Insertionsort).

Der andere Weg wäre, dass du halt immer paarweise mit dem Nachbarn vergleichst und tauscht. Wichtig, du musst natürlich auch direkt tauschen (nur ein if und in dem direkt tauschen). Sind die Nachbarn richtig sortiert, musst du halt nichts machen. Damit hast du im ersten Durchlauf garantiert das größte Element ganz rechts stehen. Das heißt, du musst deine Grenze x von 0 bis (Anzahl - 1) - y laufen lassen. Das wäre dann der Bubble-Sort, da die großen Werte wie Blasen aufsteigen.

Beide brauchen gleich lang (asymptotisch gesehen, ohne Optimierungen). Es ist eine obere Grenze für's Sortieren, wenn du Anzahl * Anzahl Schritte brauchst. Alles was darüber hinaus geht, macht ordentlich was falsch. Der ziemlich intuitivste Weg (das wäre dann der Insertionsort) braucht halt schon "nur" so lange. Aber das ist alles Theorie, die für dich erst wichtig wird, wenn du eine wirklich große Anzahl von Elementen in möglichst kurzer Zeit sortieren musst.

In deinem Code liegt der Fehler also wahrscheinlich nur im Paarweisen vergleich der Nachbarn. Dein Minimum kann damit nur aus dem letzten Paar stammen.

[Michael S.]

Zunächst nochmal VIELEN DANK! Du schreibst dir hier ja wirklich einen Wolf, um mir Begriffsstutzigen das hier zuerklären. :(
Also wenn ich deine Ausführungen verstanden hab, war es eigentlich mein Plan das "Insertionsort" zu verwenden. Ich hab den Quellcode jetzt dementsprechend geändert, aber klappen tut es immernoch nicht. Im Gegenteil: Ich bekomme zwei saftige Fehlermeldungen, wenn ich dem Array ein zweites Element hizufüge (nach jedem hizufügen soll das Array sortiert werden!) Das Array wird aber dennoch nicht sortiert: Klick 1Klick 2

Also hier mein momentaner Quelltext:

Delphi-Quellcode:

procedure Arrayordnen;
var Anzahl: integer;
    x,y: integer;
    min: tmyadress;
    minposition: integer;
begin
  anzahl:=anzahlfinden;
  Min:=MyAdress[1];
  for y:=1 to (Anzahl) Do
    begin
      For x:=y to (Anzahl) do
        begin
          if MyAdress[x].Name < Min.Name Then
            begin
              Min:= MyAdress[x];
              MinPosition:= x;
            end;
        end;
      MyAdress[MinPosition]:=MyAdress[y];
      MyAdress[y]:=min;
    end;
end;

Gruß
Michael

[Minz]

Hallo,

mit den Fehlermeldungen kann ich nicht sonderlich viel anfangen.

Da musst du mal schauen an welcher Stelle/Zeile Delphi hängen bleibt, also welche Operation gerade ausgeführt werden soll.

Desweiteren, wenn du sagst, dass eine Fehlermeldung kommt, wenn du ein zweites Element hinzufügst, stellt sich für mich die Frage, wie fügst du ein zweites Element hinzu. Desweiteren wie ist dein Array deklariert.

----
Lösung des Nicht-Sortierens:
Ich vermute einen kleinen Logikfehler in deiner Reihenfolge der Anweisungen.
Eigentlich müsstest bei jeder Incrementierung von y, Min zuweisen. Das bedeutet die Zeile

Delphi-Quellcode:

Min:=MyAdress[1];

musst du ändern in

Delphi-Quellcode:

Min:=MyAdress[y];

und diese eine Zeile nach unten verschieben, also in die 1. for-Schleife hinein.

----
Was ich sonst noch verändern würde:
Die Adressen in einem dynamischen Array ablegen. Du benötigst dann keine Extra-Funktion wie Anzahlfinden, weil du z.B. mit

Delphi-Quellcode:

for x:=low(Array) to high(Array) do begin

durch das Array laufen kannst, ohne die Anzahl kennen zu müssen.

Dann würde ich noch probieren, MyAdress[x].Name in z.B. MyAdress[x].Nachname zu ändern. In einer früheren Delphi-Version hatte ich da einmal Probleme gehabt, weil einige Datentypen .Name besitzen und es nicht eindeutig war.

Gruß Minz

[Ferber]

@Michael: Vielleicht liege ich wieder mal total daneben,
aber warum siehst Du dir nicht mal Quicksort von TStringlist an ?

[alzaimar]

... oder TList.CustomSort...

Aber wenn er den Algorithmus selbst entwickeln will, bitte sehr.
Ich denke, das es so geht. N ist die Anzahl der Elemente.

Delphi-Quellcode:

Procedure SortArray (A : TMyArray; N : Integer);
Var
  i,j,k : Integer;
  H : TArrayElement;

Begin
  For i:=0 to N-2 do begin
    k := i;                 // Position des größten Elementes initialisieren
    For j := i+1 to N-1 do // Nun wird das größte Elemente im Array [i..N-1]
      If A[k] < A[j] Then           // gesucht und in k die Position gemerkt
        k := j;  // '<' mit '>' vertauschen, wenn AUFsteigend sortiert wird.
                      // k enthält die Position des größten Elementes [i..N]
    If i <> k Then  Begin                      // Vertausche A[i] <--> A[k])
      H := A[i];
      A[i] := A[k];
      A[k] := H;
    End;
                 // A[i] enthält nun das größte Element des Arrays [i..N-1]
  End;
End;

Dann wird auch vermieden, das kleinste Element immer mitzuschleppen. Es reicht ja, sich nur den Index (hier: k) des bisher kleinsten/größten Elementes zu merken und nach dem Durchlauf das kleineste/größte Element an die Position 'i' zu kopieren, sprich: A[i] mit A[k] zu vertauschen.

[marabu]

Hallo,

so ähnlich denke ich auch. Aber warum die Daten unnütz hin und her schieben?

Delphi-Quellcode:

unit DemoTypes;

interface

uses
  Types;

type
  TAdresse = record
    Name: String;
    Vorname: String;
    Strasse: String;
    PLZ: String;
    Ort: String;
  end;

  TAdressen = array of TAdresse;

  function IndexByName(const a: TAdressen; var index: Integer): TIntegerDynArray;

implementation

uses
  SysUtils;

function MinIndex(const a: TAdressen; ida: TIntegerDynArray; iLow, iHigh: Integer): Integer;
var
  i: Integer;
begin
  Result := iLow;
  for i := Succ(iLow) to iHigh do
    if CompareText(a[ida[i]].Name, a[ida[Result]].Name) < 0 then
      Result := i;
end;

procedure SwapIndex(ida: TIntegerDynArray; i, j: Integer);
var
  iTemp: Integer;
begin
  if i <> j then
  begin
    iTemp := ida[i];
    ida[i] := ida[j];
    ida[j] := iTemp;
  end;
end;

function IndexByName(const a: TAdressen; var index: Integer): TIntegerDynArray;
var
  i: Integer;
begin
  SetLength(Result, Length(a));
  for i := Low(a) to High(a) do
    Result[i] := i;
  for i := Low(Result) to Pred(High(Result)) do
    SwapIndex(Result, i, MinIndex(a, Result, i, High(Result)));
end;

end.

Wohlgemerkt - das ist der wenig effektive Algorithmus von Michael. Ich habe ihn lediglich ein klein wenig anders implementiert und ein dynamisches Array verwendet.

Grüße vom marabu