aboutsummaryrefslogtreecommitdiffstats
path: root/Game/Code/Classes/UMergeSort.pas
blob: 8a0aa124df674a6f3d32e3133926aa1d14af8e9d (plain) (blame)
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
89
90
91
92
93
94
95
96
97
98
99
100
101
unit UMergeSort;

interface

type
	TDirection = (dSourceSource, dSourceTemp, dTempTemp, dTempSource);

	TCompareProc = function(TempIndex, SourceIndex: integer): boolean; cdecl;
  PCompareProc = ^TCompareProc;

	TCopyProc = function(iSourceIndex, iDestIndex: integer; bDirection: TDirection): boolean; cdecl;
  PCopyProc = ^TCopyProc;
	
	TMergeSorter = class
	private
		n:					integer;
		
		aCallbackCompare:	TCompareProc;
		aCallbackCopy:		TCopyProc;
		
		procedure MergeSort(lo, hi: integer);
		procedure Merge(lo, m, hi: integer);
	public
		procedure Sort(n: integer; aCompare: TCompareProc; aCopy: TCopyProc);
	end;
		

implementation

procedure TMergeSorter.Sort(n: integer; aCompare: TCompareProc; aCopy: TCopyProc);
begin
  Self.n := n;
	Self.aCallbackCompare := aCompare;
	Self.aCallbackCopy := aCopy;
  MergeSort(0, n-1);
end;

procedure TMergeSorter.MergeSort(lo, hi: integer);
var
	m:	integer;
	
begin
  if (lo<hi) then
	begin
		m := (lo+hi) div 2;
    MergeSort(lo, m);
    MergeSort(m+1, hi);
    Merge(lo, m, hi);
	end;
end;

procedure TMergeSorter.Merge(lo, m, hi: integer);
var
	i, j, k:	integer;
	
begin
	i := 0;
	j := lo;

  // vordere H�lfte von a in Hilfsarray b kopieren
  while (j<=m) do
	begin
		aCallbackCopy(j, i, dSourceTemp);
    //b[i] := a[j];
		inc(i);
		inc(j);
	end;

  i := 0;
	k := lo;
  // jeweils das n�chstgr��te Element zur�ckkopieren
  while ((k<j) and (j<=hi)) do
	begin
		if aCallbackCompare(i, j) then
    //if (b[i]<=a[j]) then
		begin
			aCallbackCopy(i, k, dTempSource);
      //a[k] := b[i];
			inc(k);
			inc(i);
    end else
		begin
			aCallbackCopy(j, k, dSourceSource);
      //a[k] := a[j];
			inc(k);
			inc(j);
		end;
	end;

  // Rest von b falls vorhanden zur�ckkopieren
  while (k<j) do
	begin
		aCallbackCopy(i, k, dTempSource);
    //a[k] := b[i];
		inc(k);
		inc(i);
	end;

end;

end.