/
basics_quicksort_ind.inc
75 lines (73 loc) · 2.06 KB
/
basics_quicksort_ind.inc
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
(*
Quicksort algorithm template (indexed data)
Usage:
--------------------------
.type _QSDataType = <Your type>; [_QSValueType = <any comparable type>]
.[<_QSGetValue or _QSCompare function body>]
.[$DEFINE COMPARABLE | COMPUTABLE]
.$I basics_quicksort_cmp.inc}
--------------------------
! if COMPARABLE defined:
. _QSDataType should be any type which can be compared with "<" operation
! if COMPUTABLE defined the following function should be defined:
.function _QSGetValue(const V: _QSDataType): _QSValueType;
.begin
. result := <some numeric expression>;
.end;
! not COMPARABLE nor COMPUTABLE defined the following function should be defined:
.function _QSCompare(const V1,V2: _QSDataType): <Some numeric type>;
.begin
. result := V1-V2; // As usual
.end;
*)const MinStack = 64;
{$DEFINE ForCodeNavigationWork}
var
i, j, L, R, Temp: Integer;
Temp2: _QSDataType;
StackPTR: Integer;
StackSize: Integer;
Stack: array[0..MinStack-1] of record
l, r: Integer;
end;
begin
for i := 0 to N-1 do Inds[i] := i;
if N < 2 then Exit;
StackSize := MinStack;
// SetLength(Stack, StackSize);
StackPTR := 0; Stack[0].l := 0; Stack[0].r := N-1;
repeat
L := Stack[StackPTR].l;
R := Stack[StackPTR].r;
Dec(StackPTR);
repeat
i := L; j := R;
Temp2 := Values[Inds[(L + R) shr 1]];
repeat
if Acc then begin
while Temp2 > Values[Inds[i]] do Inc(i);
while Temp2 < Values[Inds[j]] do Dec(j);
end else begin
while Temp2 < Values[Inds[i]] do Inc(i);
while Temp2 > Values[Inds[j]] do Dec(j);
end;
if i <= j then begin
Temp := Inds[i];
Inds[i] := Inds[j];
Inds[j] := Temp;
Inc(i); Dec(j);
end;
until i > j;
if i < R then begin
Inc(StackPTR);
if StackPTR >= StackSize then begin
Inc(StackSize, MinStack);
// SetLength(Stack, StackSize);
end;
Stack[StackPTR].l := i;
Stack[StackPTR].r := R;
end;
R := j;
until L >= R;
until StackPTR < 0;
// Stack := nil;
end;