merge sort Programm

[Koby]

Hallo ich programmier gerade am merge sort herum jedoch will es nicht funktionieren :wall:
könnte mir jemand das Programm von Grund auf erklären und wenn es möglich wäre sein beispiel schicken
wenn es jemand hat?
Vieln Dank leuts

[hanselmansel]

HiHo und willkommen in der DP,

Die Standard-Sortier-Algorithmen wurden hier im Forum schon einmal von Chäffe umfassend erläutert und dokumentiert. Merge-Sort Algorithmus Da du diesen Sort aber unter Garantie für die Schule programmieren musst, empfehle ich dir wärmstens, ihn durchzuarbeiten, ihn zu verstehen und ihn anschließend selbst zu schreiben. Denn dass der Code von Daniel von einem Profi kommt, dass sieht selbst ein blinder, inkompetenter Informatiklehrer mit Krückstock. :zwinker:

MfG,

hanselmansel

[Der_Unwissende]

Hi,
der Mergesort ist eigentlich gar nicht so schwer (merkt man leider erst wenn er fertig ist). Wichtig ist, dass du dir gut klar machst, wie er eigentlich funktioniert.
Kann dir auch nur raten zu versuchen ihn selbst zu programmieren!

Die wichtigste Grundidee ist es, dass du zwei verschiedene Schritte hast. Der erste Schritt besteht darin, dass du ein Feld in seiner Mitte teilst. Der Zweite liegt nun darin, die beiden hälften wieder sortiert zusammen zu fügen.
Das ganze rekursiv ist es auch schon.

Am leichtesten ist er zu verstehen, wenn du den mal auf einem Blatt Papier mit einem kleinen Array < 10 Elemente durchspinnst.
Nennen wir deine ganze Liste einfach A. Du zerlegst A in B und C. Sagen wir A hat 4 Elemente, dann hat B zwei und C 2. Nun machst du dass gleiche mit B und C. Als Rekursionsanker schaust du ob es mind. Zwei Elemente gibt. Also : Hat A mindestens 2 Elemente? Ja, zerlegst du in B und C (je zwei Elemente). Nun zerlegst du B (hat mindestens zwei Elemente) in B1 und B2 und C (auch zwei Elemente) in C1 und C2.
Nun machst das gleiche mit B1, B2, C1, C2. Aber jede dieser Mengen hat weniger als zwei Elemente. Ok, dann bist du mit dem zerlegen fertig (Teilproblem des Mergesorts). Nun musst du die zusammenfügen. Dazu schaust du dir B1 und B2 paarweise an. Du nimmst jetzt eine neue Liste, die so groß ist wie B1 + B2 (von der Länge, also hier 2). Dann guckst du ob B1 > B2, wenn ja, dann schreibst du B1 in die Liste, sonst B2. Dass machst du für alle Elemente von B1 und B2. Die sind dann sortiert in der Liste.
Da B1 und B2 aus B entstanden sind, ist die neue Liste also gleich dem sortierten B.
Analog für C1 und C2 sowie C.
Nennen wir die beiden Sortierten Listen B' (die aus B1 und B2 enstandene) und C' (die aus C1 und C2 enstandene). Nun weißt du, dass sie alle Elemente aus A enthalten (denn A wurde in B und C zerlegt). Also mischt du die wie gehabt. Neue Liste, für alle b aus B' einzeln gucken, ob größer als c aus C' und sortiert in die neue Liste schreiben, fertig.

Das wichtige ist hier der Divide-and-Conquer Ansatz (Teile und Herrsche). Du zerlegst dein Sortieren in sehr kleine Probleme und zwei Schritte. Du sagst, füge die sortierten Teillisten sortiert zusammen. Das ist alles.

Gruß Der Unwissende

[Koby]

erstmal vielen dank für eure schnellen antworten trotzdem wäre ich sehr
froh wenn einer mir nur ein ganz simples modell programmiert.

[hanselmansel]

:!: :!: :!:
Also erstmal dürften es einige Leute hier im Forum nicht sonderlich gerne sehen, wenn du einfach deine HA an andere delegierst. :warn: Und obwohl ich noch ein Protrait für Französisch schreiben muss:

Du suchst ein simples Beispiel? Wenn "simpel" als "kurz" verstanden werden soll, dann ist Daniel's Merge-Sort IMHO der state of the art. Was kürzeres ist kaum möglich zu programmieren.

Was kann simpel noch heißen? Sonderlich unbekannte Befehle werden ja nicht benutzt. Sind alles ziemlich einfache Strukturen.
Suchst du einen kommentierten Algorithmus? Einen Algorithmus, der in ganz viele Sub-Prozeduren zerlegt ist? (Oder suchst du einen Alogrithmus, den du Copy&Pasten kannst, ohne dass der Urheber offensichtlich wird? :mrgreen: )

Da ich felsenfest davon überzeugt bin, dass du den Algorithmus für eine Bildungsinstanz entwickeln sollst, gebe ich einen Tipp aus eigener Schüler-Erfahrung: Bei halbwegs intelligent denkenden Lehrern kommt es besser an, wenn du den Algo von Daniel ausdruckst, und auf einer DinA4-Seite Notizen dazu machst, wie er funktioniert, als einen Algo zu kopieren, von dem du dann keine Ahnung hat, wie er funktioniert.

MfG,

hanselmansel

[alzaimar]

Klick auf http://www.sortieralgorithmen.de/ und lies.

[alzaimar]

Da schreibt mir Koby doch glatt ne PN und fragt mich nach dem Quellcode.

"Nachtigall, ick hör Dir trapsen"

[hanselmansel]

Ich stelle immer wieder fest, dass ich viel zu großherzig bin... :roll: Na ja, Richard Feynman hat in der Schule bestimmt auch hin und wieder abgeschrieben, und es ist ja bekannt, wo er damit hingekommen ist: 6 Fuß unter die Erde.

[Koby]

danke leute für everything ich habe es fast geschaft! :thumb: :-D :cheers:

[Koby]

Hallo Leute ich bin nun fertig mit dem Programm und wollte nun einmal fragen ob ihr verbesserungsvorschläge habt! schreibt einfach drauf los

Delphi-Quellcode:

unit mergesort_fertig;

interface

uses
  Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
  StdCtrls;

type
  TSortierverfahren = class(TForm)
    nsortiert_lb: TListBox;
    sortiert_lb: TListBox;
    Enter_b: TButton;
    Sort_b: TButton;
    New_b: TButton;
    End_b: TButton;
    Eingabefeld_e: TEdit;
    Label1: TLabel;
    Label2: TLabel;
    Label3: TLabel;
    procedure Enter_bClick(Sender: TObject);
    procedure Sort_bClick(Sender: TObject);
    procedure FormCreate(Sender: TObject);
    procedure Mergesort(var List:array of integer);
    procedure New_bClick(Sender: TObject);
    procedure End_bClick(Sender: TObject);
  private
    { Private-Deklarationen }
  public
    { Public-Deklarationen }
  end;

var
  Sortierverfahren: TSortierverfahren;
  Elements: integer;
  nsortiert: array of integer;

implementation

{$R *.DFM}

procedure TSortierverfahren.Enter_bClick(Sender: TObject);
begin
// schreibt Zahlen in die nicht sortierte Liste ein
  Sortierverfahren.nsortiert_lb.items.add(eingabefeld_e.text);
// Array wird um 1 vergrößert
  Setlength (nsortiert,Elements+1);
// hier wird es ins Array geschrieben
  nsortiert[Elements] := (StrToInt(eingabefeld_e.text));
// die Zählvariable wird um ein erhöht
  Elements:=Elements+1;
  Sortierverfahren.eingabefeld_e.text :='';
end;

procedure TSortierverfahren.Sort_bClick(Sender: TObject);
var
  i:integer;
begin
//soll Mergesort auf die nich sortierte Liste anwenden
  Sortierverfahren.Mergesort(nsortiert);
// geht alle Zahlen durch und ...
  for i:= 0 to Elements-1 do
  begin
// ... schreibt die Zahlen sortiert in die Liste ein
    Sortierverfahren.sortiert_lb.items.add(IntToStr(nsortiert[i]));
  end;
end;

procedure TSortierverfahren.Mergesort(var List:array of integer);
var
  laenge,x,y,z: integer;
  h_array1, h_array2:array of integer;
begin
//Anzahl der zu sortierenden Elemente bestimmen
  laenge:= length(List);
//Die Hilfsfelder auf halbe Länge teilen
  Setlength (h_array1, laenge div 2);
  Setlength (h_array2,(laenge + 1) div 2);
//Zahlen aus der 1. Hälfte des Quellarray ins 1. Hilfsarray kopieren
  for x:=0 to laenge div 2 - 1 do
    h_array1[x]:=List[x];
//Das gleiche für's 2. Hilfsarray...
  for y:=0 to (laenge + 1) div 2 - 1 do
    h_array2[y]:=List[y+((laenge) div 2)];
//Wenn die Feldlänge > 2, dann rufe die Prozedur rekursiv auf.
  if laenge>2 then
  begin
    mergesort(h_array1);
    mergesort(h_array2);
  end;
  z:=0;
  while (length(h_array1) <> 0) and (length(h_array2) <>0) do
  begin
//Das oberste Element vom kleineren Stapel auswählen...
    if h_array1[0]<h_array2[0] then
    begin
//...und ins Quellarray zurückschreiben
      List[z]:=h_array1[0];
//alle Array-Elemente um 1 nach vorne schieben
      for x:=0 to length(h_array1)-2 do
      begin
        h_array1[x]:=h_array1[x+1];
      end;
//Array verkleinern
      Setlength (h_array1,length(h_array1)-1);
      end
      else
// das selbe noch mal
      begin
        List[z]:=h_array2[0];
        for y:=0 to length(h_array2)-2 do
        begin
          h_array2[y]:=h_array2[y+1];
        end;
        setlength(h_array2,length(h_array2)-1);
      end;
      z:=z+1;
    end;
    if length(h_array1)<>0 then
    begin
      for x:=0 to length(h_array1)-1 do
      begin
        List[z]:=h_array1[x];
        z:=z+1;
      end;
{Nach dem Durchlauf der Schleife ist eins der Hilfsfelder auf jeden Fall leer.
Wenn das andere noch Elemente enthält, dann wird es komplett ins Quell-Array
geschrieben.}
    end;
    if length(h_array2)<>0 then
    begin
    for y:=0 to length(h_array2)-1 do
    begin
      List[z]:=h_array2[y];
      z:=z+1;
    end;
  end;
end;


procedure TSortierverfahren.FormCreate(Sender: TObject);
begin
  Elements:=0;
end;

procedure TSortierverfahren.New_bClick(Sender: TObject);
begin
  Elements:=0;
  Sortierverfahren.sortiert_lb.clear;
  Sortierverfahren.nsortiert_lb.clear;
end;

procedure TSortierverfahren.End_bClick(Sender: TObject);
begin
 close();
end;

end.

Hoffe ihr habt ein paar gute ideen! :idea: :idea: :idea: