Mischsortieren

JayAy · Hält's aus hier Beiträge: 4

Ich wage mal einen Querpost: www.delphipraxis.net..._mischsortieren.html

Hi Leute,

ich hab zwar schon einen ähnlichen Beitrag gesehen Beitrag zu Mischsortieren, jedoch hab ich dort absolut nicht gefunden, was ich suche. Also hier mein Problem:

Ich habe - wie ich eigentlich angemommen hab - ein Programm geschrieben, dass mithilfe von Michsort Zahlen in einem Array sortieren soll. Die procedures, die ich reingeschrieben habe, müssten eigentlich zuverlässig sein, da ich sie einem Buch entnommen und wenig modifiziert habe. Das große Problem ist, dass mir die Zahlen im Stringrid in beiden Spalten gleich und damit völlig unsortiert ausgegeben werde... ich hoffe, ihr wisst Rat...

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:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:

unit Mischsortieren;

interface

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

type
    TForm1 = class(TForm)
    StringGrid1: TStringGrid;
    Button1: TButton;
    procedure Button1Click(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
  end;

var
  Form1: TForm1;
  Liste: array[1..100000] of integer;
  l: integer;


implementation

{$R *.dfm}

Procedure Mischsortieren1 (links,rechts: Integer);
var Endelinks, Anfangrechts:Integer;

Procedure Mischen1 (I,J:Integer);
var Z, K: Integer;
begin
  if I<J then
    begin
      if Liste[I]<=Liste[J] then
        begin
          Mischen1(I+1,J);
        end
      else
        begin
          z:=Liste[J];
        end;
          For k:=J-1 to I do
            begin
              Liste[K+1]:=Liste[k];
            end;
          Liste[I]:=Z;
          if J<rechts then
            begin
              Mischen1(I+1,J+1);
            end;

    end;
end;

begin
  Endelinks:=round((links+rechts)/2);
  Anfangrechts:=Endelinks+1;
  if links<Endelinks then
  begin
    Mischsortieren1(links,Endelinks);
  end;
  if Anfangrechts<rechts then
  begin
    Mischsortieren1(Anfangrechts,rechts);
  end;
  Mischen1(links,Anfangrechts);
end;

procedure TForm1.Button1Click(Sender: TObject);
begin
Randomize;
For l:= 1 to 100000 do
begin
  Liste[l]:= Random(1000)+1;
  stringgrid1.Cells[3,l]:=inttostr(Liste[l]);
end;
Mischsortieren1 (Liste[1],Liste[100000]);
For l:=1 to 100000 do
begin
  stringgrid1.Cells[4,l]:=inttostr(Liste[l]);
end;
end;

end.

SvenAbeln · Beiträge: 334 Erhaltene Danke: 3

Ich hab das jetzt nicht alles nachvollzogen aber einige Dinge sind mir schon aufgefallen.

Zeile 81: Deine Liste enthält doch Zufallszahlen, da würdest du doch jedes mal einen anderen Aufruf deiner Sortierfunktion bekommen. Müsste das nicht so aussehen?

markieren

Delphi-Quelltext

1:	Mischsortieren1 (1,100000);

Zeile 70: Warum mischt du nur die erste Hälfte von deiner Liste, was ist denn mit der oberen Hälfte?

Zeile 46: Die For Schleife kann nicht viel machen, da I<J ist. Meinst du vielleicht

markieren

Delphi-Quelltext

1:	For k:=J-1 downto I do

elundril · Verfasst: So 04.04.10 06:52

was du hier versuchst nennt sich auch MergeSort. Dazu gibt es zwei vorzügliche Wikipediaseiten. Einmal auf deutsch und einmal auf englisch. Ich denke mit diesen zwei Seiten wirst du weiterkommen, da beide den Pseudocode für Mergesort auf unterschiedliche Weise formuliert haben.

lg elundril

_________________

This Signature-Space is intentionally left blank.
Bei Beschwerden, bitte den Beschwerdebutton (gekennzeichnet mit PN) verwenden.

JayAy · Hält's aus hier Beiträge: 4

Hi, vielen Dank für die Antworten. Das mit den Indizies statt 1 und 100000 war natürlich n dummer Fehler. Ich hab jetzt auch mal 1 bis 10 statt 1 bis 100000 gewählt, damit das ganze schneller läuft. Danke auch für die Wikipediaseite, allerdings habe ich den Algorithmus ja schon verstanden und halbwegs umgesetzt, mir gehts nur noch darum, die winzigen Fehler zu finden, die es unmöglich machen, dass das Programm läuft.

Zur Zeile 70: Das hängt damit zusammen, dass Mischsort mir die Liste immer weiter aufteilt, bis nur noch Einzelelemente vorliegen, die er vermischt. Dabei wird die Grenze (Anfangrechts) für jedes Stück weiterverschoben. Hab ich eben auch noch einmal kontrolliert: stimmt mit dem Algorithmus im Bch überein.

So hier ist der neueste Stand. Mittlerweile zeigt er mir jedoch einen stack overflow an... würde ja eigentlich eher auf ne Endlosschleife hinweisen..........

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:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:

unit Mischsortieren;

interface

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

type
    TForm1 = class(TForm)
    StringGrid1: TStringGrid;
    Button1: TButton;
    procedure Button1Click(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
  end;

var
  Form1: TForm1;
  Liste: array[1..10] of integer;
  l: integer;


implementation

{$R *.dfm}

Procedure Mischsortieren1 (links,rechts: Integer);
var Endelinks, Anfangrechts:Integer;

Procedure Mischen1 (I,J:Integer);
var Z, K: Integer;
begin
  if I<J then
    begin
      if Liste[I]<=Liste[J] then
        begin
          Mischen1(I+1,J);
        end
      else
        begin
          z:=Liste[J];
        end;
          For k:=J-1 downto I do
            begin
              Liste[K+1]:=Liste[k];
            end;
          Liste[I]:=Z;
          if J<rechts then
            begin
              Mischen1(I+1,J+1);
            end;

    end;
end;

begin
  Endelinks:=round((links+rechts)/2);
  Anfangrechts:=Endelinks+1;
  if links<Endelinks then
  begin
    Mischsortieren1(links,Endelinks);
  end;
  if Anfangrechts<rechts then
  begin
    Mischsortieren1(Anfangrechts,rechts);
  end;
  Mischen1(links,Anfangrechts);
end;

procedure TForm1.Button1Click(Sender: TObject);
begin
Randomize;
For l:= 1 to 10 do
begin
  Liste[l]:= Random(10)+1;
  stringgrid1.Cells[3,l]:=inttostr(Liste[l]);
end;
Mischsortieren1 (1,10);
For l:=1 to 10 do
begin
  stringgrid1.Cells[4,l]:=inttostr(Liste[l]);
end;
end;

end.

Einloggen, um Attachments anzusehen!

SvenAbeln · Beiträge: 334 Erhaltene Danke: 3

Zu Zeile 70: Stimmt, die obere Grenze kommt in diesem Fall aus der Variable Rechts.

Der Stackoverflow kommt von deinem Round in Zeile 60, bei Mischsortieren1(1,2) bekommst du dort wieder als Endelinks := 2. Es wird also immer wieder rekursiv Mischsortieren1(1,2) aufgerufen.
Nimm dort mal Trunc.

Außerdem steht in deiner Funktion Mischen1 ein end falsch.
So müsste es passen:

markieren

Delphi-Quelltext

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

  Procedure Mischen1(I, J: integer);
  var
    Z, K: integer;
  begin
    if I < J then
    begin
      if Liste[I] <= Liste[J] then
        Mischen1(I + 1, J)
      else
      begin
        Z := Liste[J];
        For K := J - 1 downto I do
          Liste[K + 1] := Liste[K];
        Liste[I] := Z;
        if J < rechts then
          Mischen1(I + 1, J + 1);
      end;
    end;
  end;

JayAy · Hält's aus hier Beiträge: 4

Oh, stimmt.

Das ist der Hammer: Jetzt klappt's: Super!

=) Vielen vielen Dank =) und frohe Ostern! =)

Delphi-Laie · Verfasst: So 04.04.10 13:02

Kleiner Hinweis noch: Mergesort bedeutet (eher) Verschmelzungssortieren und nicht Mischsortieren, denn angelsächsisch wird es ja nicht „mix sort“ genannt. Vermischen assoziiert wegen des Kartenmischens auch eher das Erzeugen einer Unordnung, was ja nun gar nicht das Ziel des Sortierens ist.

Hidden · Verfasst: So 04.04.10 13:25

Hi

Ich hätte jetzt auch eher an den hier gedacht: de.wikipedia.org/wiki/Bogosort :mrgreen:

markieren

Delphi-Quelltext

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

Procedure Mischen1(i, j: Integer);
var
  z, k: Integer;
begin
  if i < j then begin
    if Liste[i] <= Liste[j] then
      Mischen1(i+1, j)
    else begin
      z := Liste[j];
      for k := j-1 downto i do 
        Liste[k+1] := Liste[k];
      Liste[i] := z;
      if j < rechts then
        Mischen1(i+1, j+1);
    end;
  end;
end;

Kommt dir dieser Quelltext bekannt vor? Guck mal, wie kurz der geworden ist

Frohe Ostern =)

E: vllt. liest man doch besser zuerst alle anderen Beiträge :gruebel:

Der von

SvenAbeln war schon ähnlich eingekürzt und ich dachte, das wäre der aus dem Buch also habe ich zuerst nich nahc Fehlern geguckt :oops:

.

_________________
Centaur spears can block many spells, but no one tries to block if they see that the spell is a certain shade of green. For this purpose it is useful to know some green stunning hexes. (HPMoR)

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme