Selection Sort

ChickenHotSauce · Hält's aus hier Beiträge: 6

Guten Morgen,
bin neu hier und muss ein einfaches Sortierprogramm für die Schule anfertigen. Grundlegendes habe ich schon implementiert. Bei dem Sortieralgorithmus handelt es sich um Selection Sort. Die grundlegende Idee habe ich verstanden, weiß aber nicht welche Variabeln, Listboxen, etc. ich benutzen muss. Bis jetzt habe ich das hier:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:

procedure TForm1.FormCreate(Sender: TObject);
begin
 Randomize;
end;

procedure TForm1.ClearButtonClick(Sender: TObject);
begin
 UnsortListBox.Clear; // unsortierte Zahlen und
  SortListBox.Clear; // sortierte Zahlen löschen
  for i := 1 to 10 do // 10 Zahlen zufällig
    UnsortListBox.Items.Add(IntToStr(Random(100))); // erzeugen
end;

procedure TForm1.SortButtonClick(Sender: TObject);
var i, j, min : Integer;
Begin
  For i:= 1 to N-1 Do
  Begin
    min:= i;
    For j:= i+1 To N Do
      If (Data[j] < Data[min]) Then min:= j;

    SwapValues( i, min);
  End;
end;

procedure TForm1.CloseButtonClick(Sender: TObject);
begin
 Application.Terminate; // Programm beenden
end;

end.

Bei SortButtonClick ist der Haken. Ich möchte die sortierten Zahlen in der SortListBox ausgeben. Wie?
Danke schonmal im Voraus!

Moderiert von Th69: Code- durch Delphi-Tags ersetzt
Moderiert von Th69: Delphi-Tags hinzugefügt

Th69 · Verfasst: Mi 17.02.21 13:05

Hallo,

bis jetzt hantieren deine beiden Prozeduren ClearButtonClick und SortButtonClick mit unterschiedlichen Daten.
Du solltest datenbasiert arbeiten, d.h. erst das Array Data mit Zufallszahlen füllen und diese dann in der UnsortListBox ausgeben. Gleiches dann nach dem Sortieren: erst die Daten sortieren und dann die SortedListBox (neu) füllen.

In einem größeren Projekt würde man für die Logik (bzw. Datenhaltung) eine eigene Unit erzeugen und der UI-Code würde dann darauf zugreifen (sog. Trennung von UI und Logik).

ChickenHotSauce · Hält's aus hier Beiträge: 6

Wie mach ich das? Ich weiß was du meinst, hab aber keine Ahnung von Lazarus.

Moderiert von Th69: Beiträge zusammengefasst

Idee ist, dass ich die unsortierten Zahlen aus der Unsortlistbox nehme, sortiere und in der SortListBox ausgebe. Ich suche nach der kleinsten Zahl und vertausche sie mit der ersten, dass solange bis alle von klein bis groß sortiert sind. Ich verstehe auch den Code, der da steht, aber ich weiß einfach nicht welche Variabeln, Strings, etc. ich einsetzen soll. Das letzte Programm habe ich vor Acht Monaten geschrieben, meine Erinnerung hält sich in Grenzen. Kannst du mir bitte auf die Sprünge helfen. Es soll jetzt auch kein Riesenaufwand werden, von wegen getrennte Units und so.

ub60 · Beiträge: 764 Erhaltene Danke: 127

ChickenHotSauce hat folgendes geschrieben :

meine Erinnerung hält sich in Grenzen.

OK, das merkt man

.

Aber mal wieder sachlich:

Du benötigst ein Array , z.B. Data: array[1..100] of Integer;
Dann befüllst Du das Array mit Zufallszahlen:

markieren

Delphi-Quelltext

1:
2:

  for i := 1 to 10 do // 10 Zahlen zufällig
   Data[i]:=Random(100);

Diese Zufallszahlen (Array) gibst Du in die UnsortiertListBox aus.
Dann wird das Array sortiert (da sieht Dein Quelltext schon fast gut aus).
Es fehlt leider noch die Prozedur SwapValues, die musst Du noch implementieren. Das sind einfach nur 3 Zeilen zum Tauschen.
Die sortierten Zufallszahlen (Array) gibst Du in die SortiertListBox aus.

ub60

ChickenHotSauce · Hält's aus hier Beiträge: 6

Etwa so?

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:

var
  Form1: TForm1;
  Zahlenfeld: Array[1..1000] of integer;
implementation

{$R *.lfm}

{ TForm1 }

procedure TForm1.FormCreate(Sender: TObject);
begin
 randomize;
end;

procedure TForm1.ClearButtonClick(Sender: TObject);
 Var lauf, i :integer;

 begin
   UnsortListBox.Clear;
   SortListBox.Clear;
   i := 1000;
   for lauf :=1 to i do
     begin
       Zahlenfeld[lauf]:= Random(1000);
       UnsortListBox.Items.Add(intToStr(Zahlenfeld[lauf]));
     end;
   end;

Scheint zu funktionieren. Habe jetzt noch ein Problem mit der Sortierfunktion. Die gibt nämlich manchmal Zahlen doppelt und dreifach herausgegeben werden, obwohl gar nichts so viele zum sortieren stehen. Der Code ist wie folgt:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:

procedure TForm1.SortButtonClick(Sender: TObject);
 Var
     i, j     : LongInt;
     Temp, Min: LongInt;
 Begin
     For i := Low(Zahlenfeld) To High(Zahlenfeld) Do
     Begin
         Min := i;
         For j := i+1 To High(Zahlenfeld) Do
             If Zahlenfeld[j] < Zahlenfeld[Min]
             Then
                   Min := j;
                   Temp := ZahlenFeld[Min];
                   ZahlenFeld[Min] := ZahlenFeld[i];
                   ZahlenFeld[i] := Temp;
                   sortListBox.Items.Add(intToStr(Zahlenfeld[i]));
     End;
 End;

Moderiert von Th69: Code- durch Delphi-Tags ersetzt

Th69 · Verfasst: Mi 17.02.21 21:54

Du hast zwar innerhalb der Sortierschleife den Code nach dem then logisch korrekt eingerückt (zumindestens bis auf die letzte Zeile), der Compiler jedoch interpretiert dies anders. Dir fehlt dort noch begin und end. ;-)

Edit: s. nächste Antworten

ub60 · Beiträge: 764 Erhaltene Danke: 127

Th69 hat folgendes geschrieben :

Du hast zwar innerhalb der Sortierschleife den Code nach dem then logisch korrekt eingerückt (zumindestens bis auf die letzte Zeile), der Compiler jedoch interpretiert dies anders. Dir fehlt dort noch begin und end. ;-)

Da muss ich widersprechen. Der Code ist korrekt, nur die Einrückung ist falsch.

@ChickenHotSauce:
Zahlen können mehrfach vorkommen, da sie ja zufällig erzeugt werden.

Th69 · Verfasst: Do 18.02.21 10:36

Da hast du recht, hatte mich von der Einrückung generell verwirren lassen (und hatte auch einen anderen Sortieralgo im Kopf, wie z.B. Bubblesort, wo jedesmal vertauscht wird).

Trotzdem sollten nur genau 1000 Einträge in der ListBox sein (vor dem Sortieren sollten diese aber gelöscht werden).

hRb · Beiträge: 287 Erhaltene Danke: 12

Hallo ChickenHotSauce,
Du möchtest sortieren? Na gut, Code wird, wenn die Hinweise beachtet werden funktionieren. NUR - Dein Algorithmus ist recht lahm. Denk doch mal über Quicksort nach (rekursiv sortieren). War eine meiner Prüfungsaufgaben 1962 (!)
siehe forum.lazarus.freepa...ex.php?topic=31729.0
oder de.wikipedia.org/wiki/Quicksort
wo die Sortier-Methode noch schön erklärt wird. Zahlt sich aus bei großen Datenmengen.
hRb

Gausi · Verfasst: Do 18.02.21 22:27

Ich denke mal, dass es hier um eine Art Hausaufgabe geht, für die ein einfaches Sortierverfahren implementiert werden soll, um einige Grundlagen der Programmierung zu lernen. Da ist Quicksort imho nicht so gut geeignet, da es meiner Ansicht nach auch recht anfällig für "+/-1 Fehler" ist.

Schneller ist der (im Mittel), das ist keine Frage. Eine Alternative wäre noch Mergesort, der auch eine N*log(N)-Laufzeit hat.

Aber wo wir bei dem Thema Quicksort sind, darf dieses Video nicht fehlen. :gruebel:

www.youtube.com/watch?v=ywWBy6J5gz8

_________________
We are, we were and will not be.

ub60 · Beiträge: 764 Erhaltene Danke: 127

Weil ja parallel gerade ein Thread zur Pascal-Code-Formatierung läuft:

Ich habe den diskutierten Code mal in Lazarus automatisch formatieren lassen, dann verschwindet auch die täuschende Einrückung.

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:

procedure TForm1.Button2Click(Sender: TObject);
var
  i, j: longint;
  Temp, Min: longint;
begin
  for i := Low(Zahlenfeld) to High(Zahlenfeld) do
  begin
    Min := i;
    for j := i + 1 to High(Zahlenfeld) do
      if Zahlenfeld[j] < Zahlenfeld[Min] then
        Min := j;
    Temp := ZahlenFeld[Min];
    ZahlenFeld[Min] := ZahlenFeld[i];
    ZahlenFeld[i] := Temp;
    sortListBox.Items.Add(IntToStr(Zahlenfeld[i]));
  end;
  SortListBox.Items.SaveToFile('sort.txt');
end;

ub60

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme