Mergesort für zweidimensionales Array

[tryanderror]

Hallo zusammen,

Ich möchte ein zweidimensionales Array mit Mergesort sortieren, sodass hinterher die einzelnen "Zuordnungen" im Array erhalten bleiben:

Code:

Unsortiert:        Sortiert:         Was ich vermeiden möchte (sortiert):
3, 33              1, 11             1, 33
5, 55              3, 33             3, 55
1, 11       ==>    4, 44             4, 11
4, 44              5, 55             5, 44
7, 77              7, 77             7, 77

Für ein eindimensionales Array klappt das soweit, dazu nehme ich den Delphi-Code von http://www.stefan-baur.de/cs.algo.mergesort.html
Aber lässt er sich (bzw. Mergesort allgemein) auf zweidimensionale Arrays erweitern?

Vielen Dank im Voraus!

[Dax]

So wie ich das sehe, willst du ein Array von Arrays nach dem ersten Element der Elemente aufsteigend sortieren. Das sollte eigentlich prima gehen, wenn du immer nur das erste Element zum Vergleich anfasst, aber das ganze Array für Vertauschungen/Verschiebungen/Merges benutzt.

[sx2008]

Beim Sortieren gibt es zwei grundsätzliche Operationen:
1.) Vergleichen zweier Elemente
2.) Vertauschen zweier Elemente

In deinem speziellen Fall musst du lediglich dafür sorgen, das beim Vertauchen beide Werte vertauscht werden.
Als Vorübung dazu schreibe dir eine Prozedure, die diese Vertauschung vornimmt.

Delphi-Quellcode:

// Code ungeprüft, da IDE z.Zt. defekt - aber das Prinzip sollte klarwerden
type
  TZeile = array[0..1] of integer;
  TSortArray = array[0..49] of TZeile;  //= array[0..49][0..1] of integer;

procedure SwapArrayZeile(var a, b : TZeile);
var
  c : TZeile;
begin
  c := a;
  a := b;
  b := c;
end;

[himitsu]

solange die zusammengehörigen Werte in untergeordneten Arrays liegen, ist das kein Problem

statt array of Integer dem in dem Beispielcode da drüben
einfach deine Array-Definition angeben

und dann einfach das untergeordnete Array wie eine normale Variable behandeln.

Zitat:

a = array of array[0..1] of integer

bei a[x] := a[y]; würde das gesamte Unterarray sozusagen kopiert

[tryanderror]

Erstmal vielen Dank für eure Antworten :-)

Mit Sortierverfahren kenne ich mich leider nicht wirklich aus, sodass ich eure Antworten nicht ganz verstanden habe.
Das Array, das ich sortieren möchte, heißt erstmal "test":

Code:

var test: array[0..3, 0..1] of Integer;

Ist das also ein "array of array of Integer"?

Ich habe es mal mit "array of array of Integer" versucht, sodass die Deklaration der Prozedur nun so aussieht:

Code:

procedure MergeSort(var A: array of array[0..1] of Integer);

Allerdings bekomme ich beim Kompilieren in der Zeile der Deklaration den Fehler "[Error] mMergeSort.pas(5): 'OF' expected but '(' found"

Scheinbar mag Delphi es nicht, wenn ich direkt "array of array[0..1] of Integer) schreibe - wie kann ich das "umgehen"?

[himitsu]

das geht schon alleine wegen der starken Typprüfung von Delphi nicht, selbst wenn man die Prozedure so definiert bekommt

Delphi-Quellcode:

type Ttest: array[0..3, 0..1] of Integer;

var test: Ttest;

procedure MergeSort(var A: Ttest);

[tryanderror]

Ah danke, damit bin ich schonmal einen Schritt weiter gekommen.

Jetzt bekomme ich in der Zeile

Code:

SetLength(SA, (HiL - LoL + 1) + (HiR - LoR + 1));

den Fehler "[Error] mMergesort.pas(24): Incompatible types" und der Cursor steht hinter dem "SA,".
Mir ist klar, dass - da SA jetzt ein zweidimensionales Array ist - es so nicht stehenbleiben kann. Scheinbar wird in der Zeile die Anzahl der Elemente im Array "SA" neu gesetzt (oder so ähnlich) - ich habe es mal mit

Code:

SetLength(High(SA), (HiL - LoL + 1) + (HiR - LoR + 1));

versucht, aber es schien nicht ganz richtig zu sein...
Ich hoffe ihr könnt mir weiterhelfen :-)

Ansonsten überlege ich, ob ich den Code nicht lieber selbst neu schreiben sollte. Dafür spricht sicherlich der Lerneffekt, bei Wikipedia gibt es im Abschnitt Implementierung (http://de.wikipedia.org/wiki/Mergesort#Implementierung) ja den Pseudo-Code. Ist da mit "antworte liste" "result:=liste" gemeint?
Gegen das selbst programmieren spricht momentan, dass der Code sehr effizient arbeiten muss, da ich hinterher sehr viele Daten in einem Array möglichst schnell sortieren möchte. Ich gehe mal davon aus, dass der MergeSort-Code für Delphi von der Seite, die ich oben gepostet habe, recht effizient arbeitet - und ich fürchte, dass ich als Anfänger nicht an diese Effizienz herankommen werde...

[Blup]

Bitte zeig uns doch mal deine Deklaration von SA.
Besser noch du hängst die komplette Unit an deinen Beitrag.

[tryanderror]

Okay, im Anhang befindet sich die mMergeSort.pas, an der ich bereits herumgebastelt habe, damit das MergeSort auch für zweidimensionale Arrays funktioniert.

[Blup]

Die Sortierfunktion ist auf dynamische Arrays ausgelegt, ein SetLength auf ein Array konstanter Größe ist natürlich nicht möglich.
Ich habe den Elementen, die im Array verwaltet werden, einen eigenen Typ spendiert und wie bereits vorgeschlagen eine Vergleichsfunktion angelegt. Ändert sich der Typ der Elemente, muss eigentlcih nur diese Vergleichsfunktion angepasst werden (und natürlich auch UnitTest).