blob: 8d61ee447b730dda96e08d7c3c6f93d6e8a879d7 (
plain)
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
|
// SortTools_HeapSort.gxx
// cree le 04/11/91 par ASI
// Reference : Software Conponents with ADA, Grady Booch.
void Shift(Array& TheArray,
const Comparator& Comp,
const Standard_Integer Left, const Standard_Integer Right)
{
Item Temp = TheArray(Left);
Standard_Integer Front = Left;
Standard_Integer Back = Front * 2;
while (Back <= Right) {
if (Back < Right) {
if(Comp.IsLower(TheArray(Back), TheArray(Back + 1))) {
Back = Back + 1;
}
}
if(!Comp.IsLower(Temp, TheArray(Back))) break;
TheArray(Front) = TheArray(Back);
Front = Back;
if(Front * 2 > TheArray.Upper()) break;
Back = Front * 2;
}
TheArray(Front) = Temp;
}
void SortTools_HeapSort::Sort(Array& TheArray,
const Comparator& Comp)
{
Item TempItem;
Standard_Integer Left;
Standard_Integer Right;
Left = ((TheArray.Upper() - TheArray.Lower() + 1) / 2) + 1;
Right = TheArray.Upper();
while (Left > TheArray.Lower()) {
Left = Left - 1;
Shift(TheArray, Comp, Left, Right);
}
while (Right > TheArray.Lower()) {
TempItem = TheArray(TheArray.Lower());
TheArray(TheArray.Lower()) = TheArray(Right);
TheArray(Right) = TempItem;
Right = Right - 1;
Shift(TheArray, Comp, Left, Right);
}
}
|
