Sortieralgorithmen

Für Fragen von Einsteigern und Programmieranfängern...
Antworten
LazarusPleb
Beiträge: 10
Registriert: Do 5. Okt 2017, 18:05

Sortieralgorithmen

Beitrag von LazarusPleb »

Guten Tag,
ich habe ein Problem mit Sortieralgorithmen, die ich nicht ganz verstehe.
Im Unterricht haben wir uns mit Bubble Sort, Double Sort und Shakersort befasst.
Mein Problem liegt bei Double Sort. Ich finde dazu nichts im Internet, aber ich habe den Code für ein Programm damit.
Kann mir jemand bitte sagen, ob das vielleicht unter einem anderen Namen bekannt ist oder weis jemand wo man dazu Erkärungen bzw. Erläuterungen findet?

(Der wichtige Teil des Quellcodes befindet sich in: procedure TForm1.B_ordnenClick(Sender: TObject);
)
Vielen Dank im Vorraus.

Code: Alles auswählen

unit Unit1;
 
{$mode objfpc}{$H+}
 
interface
 
uses
  Classes, SysUtils, FileUtil, Forms, Controls, Graphics, Dialogs, StdCtrls;
 
type
 
  { TForm1 }
 
  TForm1 = class(TForm)
    B_ordnen: TButton;
    B_zahlen: TButton;
    LB_ausgabe: TListBox;
    LB_ausgabe2: TListBox;
    procedure B_ordnenClick(Sender: TObject);
    procedure B_zahlenClick(Sender: TObject);
    procedure FormCreate(Sender: TObject);
  private
    { private declarations }
  public
    { public declarations }
  end;
 
var
  Form1: TForm1;
   zahlen: ARRAY[1..21] of Integer;
  i,k,g,z,Zufall: Integer;
implementation
 
 
{$R *.lfm}
 
{ TForm1 }
 
procedure TForm1.FormCreate(Sender: TObject);
begin
  randomize
end;
 
procedure TForm1.B_zahlenClick(Sender: TObject);
begin
 
i:=0;
REPEAT
  i:=i+1;
  Zufall:=Random(100)+1;
  zahlen[i]:=Zufall;
  LB_Ausgabe.Items.Add(InttoStr(zahlen[i]));
  until i=20  ;
end;
 
procedure TForm1.B_ordnenClick(Sender: TObject);
begin
  LB_Ausgabe2.clear ;
  z:=0;
  i:=0;
  g:=0;
REPEAT
  i:=0;
  k:=101;
  Repeat
  i:=i+1;
  IF zahlen[i] < k Then IF zahlen[i] > g Then k:=Zahlen[i];
  until i=20;
  z:=z+1;
  g:=k;
  LB_Ausgabe2.Items.Add(InttoStr(k));
until z= 19  ;
 
end;
 
end.
 

siro
Beiträge: 730
Registriert: Di 23. Aug 2016, 14:25
OS, Lazarus, FPC: Windows 11
CPU-Target: 64Bit
Wohnort: Berlin

Re: Sortieralgorithmen

Beitrag von siro »

Hallo,
ich habe ein englisches Dokument gefunden, evtl. hilft es Dir weiter.

gibt mal Double Sort als zwei Wörter ein, da findet man doch so einiges.

Siro
Dateianhänge
Double_Sort.pdf
(446.78 KiB) 89-mal heruntergeladen
Grüße von Siro
Bevor ich "C" ertragen muß, nehm ich lieber Lazarus...

braunbär
Beiträge: 369
Registriert: Do 8. Jun 2017, 18:21
OS, Lazarus, FPC: Windows 10 64bit, Lazarus 2.0.10, FPC 3.2.0
CPU-Target: 64Bit
Wohnort: Wien

Re: Sortieralgorithmen

Beitrag von braunbär »

Wo hast du um Gottes Willen diesen grauenhaften Code her?

- Keinerei Kommentare
- Völig nichtssagende Variablennamen, noch dazu lauter globale statt lokale variable
- repeat-Schleifen, wo for-Schleifen angebracht wären
- Das Feld Zahlen wird selbst gar nicht sortiert, sondern die Zahlen werden nur in die Ausgabelistbox geschaufelt
- Prinzipiell sollte man die Programmlogik von den Ereignisbehandlungsroutinen trennen
- Das Programm ist noch dazu fehlerhaft: Wenn zufällig beim Initialisieren in dem Feld mehrmals die gleiche Zahl generiert wird, funktioniert es nicht mehr, weil in jedem Durchlauf nach einer Zahl gesucht wird, die grösser ist als die bisher schon ausgegebenen Zahlen. Jede Zahl wird folglich nur einmal in die Ausgabeliste aufgenommen, und am Ende findet er keine passende Zahl mehr und gibt folglich den Wert 101 aus, mit dem k am Anfang jedes Durchlaufs initiaisiert wird.

Der Sort funktioniert nach dem Prizip, dass in jedem äusseren Schleifendurchauf die kleinste Zahl gesucht wird, die noch nicht in die Ausgabeliste übertragen worden ist. Die größte Zahl, die schon "erledigt" ist, merkt es sich in der Variable g, die im aktuellen Durchlauf kleinste noch nicht erledigte Zahl in der Variable k.

Hier das ganze in halbwegs lesbarer Form, dann verstehst du vielleicht besser, wie das fuktioniert (der Fehler ist hier aber nicht behoben).

Code: Alles auswählen

 
 unit Unit1;
 
{$mode objfpc}{$H+}
 
interface
 
uses
  Classes, SysUtils, FileUtil, Forms, Controls, Graphics, Dialogs, StdCtrls;
 
const
maxzahl=100// grösste Zahl
maxindex=20// Feldgrösse
 
type
 
  { TForm1 }
 
  TForm1 = class(TForm)
    B_ordnen: TButton;
    B_zahlen: TButton;
    LB_ausgabe: TListBox;
    LB_ausgabe2: TListBox;
    procedure B_ordnenClick(Sender: TObject);
    procedure B_zahlenClick(Sender: TObject);
    procedure FormCreate(Sender: TObject);
  private
    { private declarations }
  public
    { public declarations }
  end;
 
var
  Form1: TForm1;
  zahlen: ARRAY[1..maxindex] of Integer;
 
implementation
 
 
{$R *.lfm}
 
procedure Feld_Initialisieren;
var i: integer;
begin
  LB_Ausgabe.Clear;
  for i:=1 to maxindex do
    begin
    Zahlen[i]:=Random(maxzahl)+1; // Zufallszahl zwischen 1 und maxzahl
    LB_Ausgabe.Items.Add(InttoStr(zahlen[i]))
    end;
end;
 
procedure Sortierte_Ausgabe;
// funktioniert aber nur, wenn im Feld nur verschiedene Zahlen vorkommen
var durchlauf,i, grösstes_erledigtes, kleinstes_gefundenes: integer; 
begin
  LB_Ausgabe2.clear ;
  grösstes_erledigtes := 0;
  for durchlauf:=1 to maxindex do 
    begin // In jedem Durchlauf die kleinste noch nicht erledigte Zahl ausgeben
      kleinstes_gefundenes:=maxzahl+1;
      for i:=1 to maxindex do
        if (zahlen[i]<kleinstes_gefundenes) and (zahlen[i]>grösstes_erledigtes)
        then kleinstes_gefundenes:=zahlen[i];
      LB_Ausgabe2.Items.Add(InttoStr(kleinstes_gefundenes));
      grösstes_erledigtes:=kleinstes_gefundenes;
    end
end;
 
 
{ TForm1 Ereigisbehandlung }
 
procedure TForm1.FormCreate(Sender: TObject);
begin
  randomize
end;
 
procedure TForm1.B_zahlenClick(Sender: TObject);
begin
  Feld_Initialisieren
ened;
 
procedure TForm1.B_ordnenClick(Sender: TObject);
begin
  Sortierte_Ausgabe;
end;
 
end.
 
 


edit:

Und hier noch eine Variation, die den Fehler korrigiert, indem man sich von einem Durchlauf zum nächsten merkt, an welcher Position die kleinste Zahl gefunden wurde

Code: Alles auswählen

 
procedure Sortierte_Ausgabe;
var durchlauf,i, grösstes_erledigtes, kleinstes_gefundenes,
    i_grösstes, i_kleinstes: integer;
begin
  LB_Ausgabe2.clear ;
  grösstes_erledigtes := 0; i_grösstes:=maxindex+1;
  for durchlauf:=1 to maxindex do 
    begin // In jedem Durchlauf die kleinste noch nicht erledigte Zahl ausgeben
      kleinstes_gefundenes:=maxzahl+1;
      for i:=1 to maxindex do
        if (zahlen[i]>grösstes_erledigtes)   // ist noch nicht ausgegeben worden
        and (zahlen[i]<kleinstes_gefundenes) // kleinste noch nicht ausgegebene Zahl
        then begin
             kleinstes_gefundenes:=zahlen[i];
             i_kleinstes:=i
             end
        else
        if (zahlen[i]=grösstes_erledigtes) // Zahl, gleich gross wie die im vorigen Durchgang ausgegebene
        and (i>i_grösstes)                 // aber weiter hinten im Feld 
        then begin
             kleinstes_gefundenes:=zahlen[i]// die Zahl noch einmal ausgeben
             i_kleinstes:=i;
             // Das break ist hier unbedingt nötig, für den Fall,
             // dass drei oder mehr gleich grosse Zahlen im Feld vorkommen             
             break;     
             end;     
      LB_Ausgabe2.Items.Add(InttoStr(kleinstes_gefundenes));
      grösstes_erledigtes:=kleinstes_gefundenes;                   
      i_grösstes := i_kleinstes; 
    end
end;
 

siro
Beiträge: 730
Registriert: Di 23. Aug 2016, 14:25
OS, Lazarus, FPC: Windows 11
CPU-Target: 64Bit
Wohnort: Berlin

Re: Sortieralgorithmen

Beitrag von siro »

Sehr schön dokumentiert braunbär.
Mit diesem Code kann ich auch etwas anfangen.
Ich kannte diesen Sortieralgorythmus übrigens auch noch nicht.
var a..z:Integer; ist auch nicht so mein Ding, aber wie man sieht geht es ja auch anders...
Grüße von Siro
Bevor ich "C" ertragen muß, nehm ich lieber Lazarus...

Leop02
Beiträge: 1
Registriert: Sa 7. Okt 2017, 08:13

Re: Sortieralgorithmen

Beitrag von Leop02 »

Sehr schön dokumentiert braunbär.

braunbär
Beiträge: 369
Registriert: Do 8. Jun 2017, 18:21
OS, Lazarus, FPC: Windows 10 64bit, Lazarus 2.0.10, FPC 3.2.0
CPU-Target: 64Bit
Wohnort: Wien

Re: Sortieralgorithmen

Beitrag von braunbär »

Danke :D

MacWomble
Lazarusforum e. V.
Beiträge: 999
Registriert: Do 17. Apr 2008, 01:59
OS, Lazarus, FPC: Mint 21.1 Cinnamon / FPC 3.2.2/Lazarus 2.2.4
CPU-Target: Intel i7-10750 64Bit
Wohnort: Freiburg

Re: Sortieralgorithmen

Beitrag von MacWomble »

Leop02 ist wohl Fake, will nur den Backlink den er in den Code eingebaut hat ...
Alle sagten, dass es unmöglich sei - bis einer kam und es einfach gemacht hat.

Benutzeravatar
m.fuchs
Lazarusforum e. V.
Beiträge: 2636
Registriert: Fr 22. Sep 2006, 19:32
OS, Lazarus, FPC: Winux (Lazarus 2.0.10, FPC 3.2.0)
CPU-Target: x86, x64, arm
Wohnort: Berlin
Kontaktdaten:

Re: Sortieralgorithmen

Beitrag von m.fuchs »

Die werden auch immer besser, habe ich beim Überfliegen nicht gesehen und ihn nur für einen Fullquottel gehalten.

Das Zitat ist weg, das Lob lasse ich mal stehen.
Software, Bibliotheken, Vorträge und mehr: https://www.ypa-software.de

Achtzig
Beiträge: 90
Registriert: Mo 15. Okt 2007, 13:09
OS, Lazarus, FPC: Debian
CPU-Target: xxBit

Re: Sortieralgorithmen

Beitrag von Achtzig »

Leop02 hat das Lob doch auch nur von siro übernommen, so wie er den Quelltext von weiter oben kopiert hat. Meiner Meinung nach ist Leop02 nur ein billiger Bot, der Kommentare zusammenstückelt.

Antworten