Sortieralgorithmen

Für Fragen von Einsteigern und Programmieranfängern...

Sortieralgorithmen

Beitragvon LazarusPleb » 5. Okt 2017, 17:15 Sortieralgorithmen

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.
 
LazarusPleb
 
Beiträge: 6
Registriert: 5. Okt 2017, 17:05

Beitragvon siro » 6. Okt 2017, 09:27 Re: Sortieralgorithmen

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
Du hast keine ausreichende Berechtigung, um die Dateianhänge dieses Beitrags anzusehen.
Grüße von Siro
"C" verCehnfacht die Entwicklungszeit...
siro
 
Beiträge: 222
Registriert: 23. Aug 2016, 13:25
Wohnort: Berlin
OS, Lazarus, FPC: Windows 7 Windows 8.1 Windows 10 | 
CPU-Target: 64Bit
Nach oben

Beitragvon braunbär » 6. Okt 2017, 10:28 Re: Sortieralgorithmen

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;
 
braunbär
 
Beiträge: 164
Registriert: 8. Jun 2017, 17:21

Beitragvon siro » 6. Okt 2017, 21:01 Re: Sortieralgorithmen

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
"C" verCehnfacht die Entwicklungszeit...
siro
 
Beiträge: 222
Registriert: 23. Aug 2016, 13:25
Wohnort: Berlin
OS, Lazarus, FPC: Windows 7 Windows 8.1 Windows 10 | 
CPU-Target: 64Bit
Nach oben

Beitragvon Leop02 » 7. Okt 2017, 07:16 Re: Sortieralgorithmen

Sehr schön dokumentiert braunbär.
Leop02
 
Beiträge: 1
Registriert: 7. Okt 2017, 07:13

Beitragvon braunbär » 8. Okt 2017, 21:35 Re: Sortieralgorithmen

Danke :D
braunbär
 
Beiträge: 164
Registriert: 8. Jun 2017, 17:21

Beitragvon MacWomble » 8. Okt 2017, 21:55 Re: Sortieralgorithmen

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.
MacWomble
 
Beiträge: 363
Registriert: 17. Apr 2008, 00:59
Wohnort: Freiburg
OS, Lazarus, FPC: Mint 18.1 Cinnamon / CodeTyphon Generation V Plan 6.00 (FPC 3.1.1) | 
CPU-Target: 32/64 Nit
Nach oben

Beitragvon m.fuchs » 8. Okt 2017, 21:57 Re: Sortieralgorithmen

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
m.fuchs
 
Beiträge: 1670
Registriert: 22. Sep 2006, 18:32
Wohnort: Berlin
OS, Lazarus, FPC: Winux (L 1.6, FPC 3.0) | 
CPU-Target: x86, x64, arm
Nach oben

Beitragvon Achtzig » 9. Okt 2017, 02:48 Re: Sortieralgorithmen

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.
Achtzig
 
Beiträge: 82
Registriert: 15. Okt 2007, 12:09
OS, Lazarus, FPC: Debian | 
CPU-Target: xxBit
Nach oben

• Themenende •

Zurück zu Einsteigerfragen



Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 1 Gast

porpoises-institution
accuracy-worried