Entwickler-Ecke
Sonstiges (Delphi) - Mischsortieren
JayAy - Sa 03.04.10 23:03
Titel: Mischsortieren
Ich wage mal einen Querpost: http://www.delphipraxis.net/topic176104_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...
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
public
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 - So 04.04.10 00:18
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?
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
Delphi-Quelltext
1:
| For k:=J-1 downto I do |
JayAy - So 04.04.10 08:13
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..........
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
public
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. |
SvenAbeln - So 04.04.10 11:33
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:
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 - So 04.04.10 11:46
Oh, stimmt.
Das ist der Hammer: Jetzt klappt's: Super!
=) Vielen vielen Dank =) und frohe Ostern! =)
Delphi-Laie - 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 - So 04.04.10 13:25
Hi :)
Ich hätte jetzt auch eher an den hier gedacht:
http://de.wikipedia.org/wiki/Bogosort :mrgreen:
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 8)
Frohe Ostern =)
E: vllt. liest man doch besser zuerst alle anderen Beiträge :gruebel: :D 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:.
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2026 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!