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
|
// SortTools_QuickSort.gxx
// cree le 04/11/91 par ASI
// Reference : Software Conponents with ADA, Grady Booch.
inline void Exchange(Item& Left, Item& Right)
{
Item Temp = Left;
Left = Right;
Right = Temp;
}
static void SortRecursive(Array& TheArray,
const Comparator& Comp,
const Standard_Integer Left,
const Standard_Integer Right)
{
Item Pivot;
Standard_Integer Front, Back, Middle;
if(Left < Right) {
Middle = (Left + Right) / 2;
if(Comp.IsLower(TheArray(Middle), TheArray(Left))) {
Exchange(TheArray(Middle), TheArray(Left));
}
if(Comp.IsLower(TheArray(Right), TheArray(Left))) {
Exchange(TheArray(Right), TheArray(Left));
}
if(Comp.IsLower(TheArray(Right), TheArray(Middle))) {
Exchange(TheArray(Right), TheArray(Middle));
}
Pivot = TheArray(Middle);
Exchange(TheArray(Middle), TheArray(Right - 1));
Front = Left + 1;
Back = Right - 1;
if(Back != TheArray.Lower()) {
Back = Back - 1;
}
for(;;) {
while (Comp.IsLower(TheArray(Front), Pivot)) {
Front = Front + 1;
}
while (Comp.IsLower(Pivot, TheArray(Back))) {
Back = Back - 1;
}
if(Front <= Back) {
if(Front == TheArray.Upper()) return;
if(Back == TheArray.Lower()) return;
Exchange(TheArray(Front), TheArray(Back));
Front = Front + 1;
Back = Back - 1;
}
if(Front > Back) break;
}
SortRecursive(TheArray, Comp, Left, Back);
SortRecursive(TheArray, Comp, Front, Right);
}
}
void SortTools_QuickSort::Sort(Array& TheArray,
const Comparator& Comp)
{
SortRecursive(TheArray, Comp, TheArray.Lower(), TheArray.Upper());
}
|
