MergeSort Fehler

anx · Beiträge: 16

Hallo ich versuche schon lange den MergeSort zu implementieren. Jedoch quält mich ein Fehler. Das sortierte Array fängt immer mit einer 0 an. Warum?? Ich habe zwei Buttons. Der eine zeigt das unsortierte Array, der andere das sortierte. Das Array "arr" ist global:

Hier der Code

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:

procedure Merge(iBegin,iEnd:integer);
var iMitte,i,j,k,index:integer; temp:array[0..5] of integer;
begin
 for i:=0 to 5 do
  temp[i]:=0;
 if(iEnd-iBegin>1) then begin
  iMitte:=Trunc((iBegin+iEnd)/2);
  Merge(iBegin,iMitte);
  Merge(iMitte,iEnd);

  i:=iBegin;
  j:=iMitte;
  k:=0;

  while(i<iMitte) and (j<iEnd) do
  begin
   if(arr[i] < arr[j]) then
   begin
    temp[k]:=arr[i];
    inc(i);
   end

   else
   begin
    temp[k]:=arr[j];
    inc(j);
   end;
   inc(k);
  end;


  while(i<iMitte) do
  begin
   temp[k]:=arr[i];
   inc(i);
   inc(k);
  end;

  while(j < iEnd) do
  begin
   temp[k]:=arr[j];
   inc(j);
   inc(k);
  end;

  for index:=0 to iEnd-iBegin do
  arr[index+iBegin]:=temp[index]



 end;
end;


procedure TForm1.FormCreate(Sender: TObject);
var i:integer;
begin
 randomize();
 for i:=0 to 5 do
  arr[i]:=0;
end;

procedure TForm1.Button2Click(Sender: TObject);
var i:integer;
begin
  Label2.Caption:='';
      for i:=0 to 5 do
   arr[i]:=random(45);
    Merge(0,5);

    for i:=0 to 5 do
   Label2.Caption:=Label2.Caption + '  ' + IntToStr(arr[i]);

end;

procedure TForm1.Button1Click(Sender: TObject);
var i:integer;
begin
 Label1.Caption:='';
  for i:=0 to 5 do
   arr[i]:=random(45);


    for i:=0 to 5 do
   Label1.Caption:=Label1.Caption + '  ' + IntToStr(arr[i]);

end;

Vielen dank
lg, anx

Moderiert von Narses: Code- durch Delphi-Tags ersetzt

Marc. · Verfasst: So 29.11.09 16:50

Hi und

im Forum!

anx hat folgendes geschrieben :

Ich habe zwei Buttons. Der eine zeigt das unsortierte Array, der andere das sortierte. Das Array "arr" ist global:

Beide Buttons stellen zwei völlig unterschiedliche Arrays dar, da du bei jedem Aufruf die Felder mit neuen zufälligen Werten belegst.

Zu deinem Fehler:

markieren

Delphi-Quelltext

15:	{ ... } while(i<iMitte) and (j<=iEnd) do

Du musst auf kleiner-gleich prüfen, sonst ignorierst Du die erste und letzte Zahl.

(Edit: Da muss noch mehr oder etwas anderes falsch sein) :oops:

Ich guck gleich noch mal genauer hin.

Grüße,
Marc

anx · Beiträge: 16

Hallo,
vielen Dank für die Antwort. Ich brauche den Code wenn es geht noch heute. Es ist so, dass ich C++ler bin und den Code übersetzt habe. Wichtig ist, dass hier auf keinen Fall mit dynamischer Speicherverwaltung oder z.B. Arrayübergabe mit Parameter (daher auch global) gearbeitet wird.

In C++ funktioniert der Code jedoch weshalb ich nicht weiß wo der Fehler liegt. Wäre echt lieb wenn ihr mir helfen könntet. Bei beiden Button bearbeitet ich doch das gleiche Array, da es doch global ist?!

Bitte helft mit weiter.

Vielen Dank
lg, anx

Marc. · Verfasst: So 29.11.09 19:44

Ich habe deinen Code etwas formatiert und etwas angepasst.

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:

procedure TForm1.Merge(iBegin,iEnd:integer);
var iMitte,
     i,j,k,
     index:integer;
     temp:array[0..5] of integer;
begin
   if (iEnd - iBegin > 1) then
   begin
      for i:=0 to 5 do
        temp[i]:= 0;

      iMitte := (iBegin + iEnd) div 2;
      Merge(iBegin,iMitte);
      Merge(iMitte,iEnd);

      i := iBegin;
      j := iMitte;
      k := 0;

      while (i < iMitte) and (j < iEnd) do
      begin
         if (arr[i] < arr[j]) then
         begin
            temp[k] := arr[i];
            inc(i);
         end
         else
         begin
            temp[k] := arr[j];
            inc(j);
         end;
         inc(k);
      end;

      while (i < iMitte) do
      begin
         temp[k] := arr[i];
         inc(i);
         inc(k);
      end;

      while (j <= iEnd) do    // <= instead of <
      begin
         temp[k] := arr[j];
         inc(j);
         inc(k);
      end;

      for index := 0 to iEnd-iBegin do
        arr[index+iBegin] := temp[index]
  end;
end;

Rufst Du die Prozedure nun mit den Grenzen 0 und 5+1, i.e. Merge(0,6);, funktioniert's tadellos, ansonsten wird das letzte Element beim Sortieren ignoriert. :zwinker:

Falls das bei deiner original C++ Funktion nicht der Fall war, wäre es vielleicht nicht verkehrt den entsprechen Code hier noch einmal anzuhängen.

Grüße

bsthl · Hält's aus hier Beiträge: 1

hallo anx,

.. hast Du ein Element zuviel kopiert, in Zeile 46 muss stehen:

for index:=0 to iEnd-iBegin-1 do
arr[index+iBegin]:=temp[index]

oder - vielleicht leichter lesbar:

for index := iBegin to iEnd-1 do
arr [index] := temp [index-iBegin];

Gruss,
rb

anx · Beiträge: 16

Hallo,
vielen Dank euch zwei. Das alles sieht nun schon viel besser aus. Wenn ich nun Merge mit 0,5 als Parameter aufrufe, dann wird alles sortiert bis auf das letzte Element-->wie ihr gesagt habt. Wenn ich aber nicht 5 sondern 6 schreibe, dann kommt eine Zugriffsverletzung, doch nun wird alles trotzdem richtig sortiert. Ich kann mir noch eine unsaubere Arbeit mit arrays vostellen oder habt ihr eine Idee wo die kryptische Zugriffsverletzung kommt?

Bei meinem C++ Code rufe ich Merge aber "richtig" also mit den Parametern 0,5 auf. Außerdem muss ich nicht <= schreiben. Hier ist mal mein C++ Code. Ich arbeite aber dynamschen Arrays und Arrayübergabe als Parameter. Das soll in Delphi nicht passieren, sondern erstmal auf der globalen Ebene bleiben:

markieren

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:

void TSort::MergeSort(int iBegin, int iEnd)
{
  if(iEnd-iBegin<=1)
   return;
  int iMitte=(iBegin+iEnd)/2;
  MergeSort(iBegin,iMitte);
  MergeSort(iMitte,iEnd);

  int i = iBegin;
  int j = iMitte;
  int k = 0;
  int* ipTemp = new int[iEnd-iBegin];
  while (i < iMitte && j < iEnd)
  {
   if (arr[i] < arr[j]) {
    ipTemp[k] = arr[i];
    ++i;
   }
   else
   {
    ipTemp[k] = arr[j];
    ++j;
   }
   ++k;
  }
  while (i < iMitte)
  {
   ipTemp[k] = arr[i];
    ++i;
    ++k;
   }
  while (j < iEnd)
  {
    ipTemp[k] = arr[j];
    ++j;
    ++k;
   }
  for (int iIndex = 0; iIndex < iEnd-iBegin; ++iIndex) {
   arr[iIndex+iBegin] = ipTemp[iIndex];
  }
  delete [] ipTemp;
}

Vielen, vielen Dank für eure bisherige Hilfe. Bitte helft mir auch weiterhin

.

lg,anx

PS.: arr ist ein Array, dass als privat der Klasse TSort deklariert ist.
PPS.: Ich stelle gerade fest, weshalb die Zugriffsverletzung kommt. Es ist nicht richtig <= (bei while (j <= ) iEnd)) zu schreiben. Mich hat das schon gewundert, denn auch in meinem C++ habe ich nicht <= geschrieben. Das einzig KOmische ist nun noch, dass der zweite Parameter von Merge immer um eins größer sein muss. Wisst ihr warum?

Marc. · Verfasst: So 29.11.09 22:26

anx hat folgendes geschrieben :

PPS.: Ich stelle gerade fest, weshalb die Zugriffsverletzung kommt. Es ist nicht richtig <= (bei while (j <= ) iEnd)) zu schreiben. Mich hat das schon gewundert, denn auch in meinem C++ habe ich nicht <= geschrieben. Das einzig KOmische ist nun noch, dass der zweite Parameter von Merge immer um eins größer sein muss. Wisst ihr warum?

Bei mir kommt keine AV. Ich habe aber Deinen C++-Quelltext soeben ausprobiert (1:1 kopiert) und auch hier wird bei mir das letzte Element ignoriert. Kann das sein? :gruebel:

anx · Beiträge: 16

Hallo,
bei mir funktioniert mein C++ Code. Ich rufe ihn so auf, wobei "size" die Arraygröße ist:

Sort.MergeSort(0,Sort.give_size());

Ich kann vielleicht anders fragen: Kannst Du oder ihr euch vorstellen, warum ich gerade hier den parameter um 1 höher machen muss, damit alles funktioniert. Meine Vermutung ist, dass ich mich bei der Arraydurchzählung vertue, weshalb bei "korrektem" Aufruf auch ein Element unbeachtet bleibt.

Vielen Dank nochmal
lg, anx

Marc. · Verfasst: So 29.11.09 22:40

Nein, bei Deinem Code stimmt alles! Die linke Grenze gibt den Index des ersten zu sortierenden Elements an. Die rechte Grenze steht dagegen für die Anzahl der zu sortierenden Elemente ab der linken Grenze. Also hieße Merge(0, 6): Sortiere ab dem Element 0 die folgenden 6 Elemente und somit das komplette Array.

Ich hoffe, dass ist nun so korrekt.

Edit: Das kann so nicht vollständig stehen bleiben. Ich hab' heut irgendwo ein großes Brett vorm Kopf. Ich meld mich besser morgen noch einmal.

anx · Beiträge: 16

Aber beim C++ muss ich auch nur von 0 bis 5 den Algorithmus laufen lassen. In Delphi wird doch nicht anders gezählt, wenn Du meinst, dass 6 die anzahl der zu sortierenden Element sind. In C++ habe ich mit dem zweiten Parameter die recht grenze gekennzeichnet, also 5.

Vielen Dank dir!
lg, anx

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme