Rheolef
7.1
an efficient C++ finite element environment
msg_sort_with_permutation.h
Go to the documentation of this file.
1
#ifndef _RHEOLEF_MSG_SORT_WITH_PERMUTATION_H
2
#define _RHEOLEF_MSG_SORT_WITH_PERMUTATION_H
3
/*
24
sort_with_permutation - Computes the permutation of values that gives
25
a sorted sequence.
26
27
Input Parameters:
28
v - values to sort. Unchanged
29
p - permutation array. Must be initialized to 0:n-1 on input.
30
n - number of values to sort
31
32
Notes:
33
inspirated from petsc-2.0.22/sortip.c
34
with a bug fix in quicksort as in http://iulib.googlecode.com/hg/colib/quicksort.h
35
*/
36
37
#include "rheolef/compiler.h"
38
namespace
rheolef
{
39
40
template
<
class
RandomIterator,
class
SizeRandomIterator,
class
Size>
41
void
42
quick_sort_with_permutation
(
43
RandomIterator v,
44
SizeRandomIterator
p
,
45
Size start,
46
Size end)
47
{
48
if
(start + 1 >= end)
return
;
49
typedef
typename
std::iterator_traits<RandomIterator>::value_type
T
;
50
const
T
& pivot = v[
p
[(start+end-1)/2]];
51
Size lo = start, hi = end;
52
for
(;;) {
53
while
(lo < hi && v[
p
[lo]] < pivot) lo++;
54
while
(lo < hi && v[
p
[hi-1]] >= pivot) hi--;
55
if
(lo == hi || lo+1 == hi)
break
;
56
std::swap (
p
[lo],
p
[hi-1]);
57
lo++; hi--;
58
}
59
Size split1 = lo;
60
hi = end;
61
for
(;;) {
62
while
(lo < hi && v[
p
[lo]] == pivot) lo++;
63
while
(lo < hi && v[
p
[hi-1]] > pivot) hi--;
64
if
(lo == hi || lo+1 == hi)
break
;
65
std::swap (
p
[lo],
p
[hi-1]);
66
lo++; hi--;
67
}
68
Size split2 = lo;
69
quick_sort_with_permutation
(v,
p
, start, split1);
70
quick_sort_with_permutation
(v,
p
, split2, end);
71
}
72
template
<
class
RandomIterator,
class
SizeRandomIterator,
class
Size>
73
void
74
bubble_sort_with_permutation
(
75
RandomIterator v,
76
SizeRandomIterator
p
,
77
Size
n
)
78
{
79
for
(Size k = 0; k <
n
; k++) {
80
Size vk = v [
p
[k]];
81
for
(Size j = k+1; j <
n
; j++) {
82
if
(vk > v [
p
[j]]) {
83
std::swap (
p
[k],
p
[j]);
84
vk = v [
p
[k]];
85
}
86
}
87
}
88
}
89
template
<
class
RandomIterator,
class
SizeRandomIterator,
class
Size>
90
void
91
sort_with_permutation
(
92
RandomIterator v,
93
SizeRandomIterator
p
,
94
Size
n
)
95
{
96
const
Size n_qsort_min = 8;
97
if
(
n
>= n_qsort_min) {
98
quick_sort_with_permutation
(v,
p
, Size(0),
n
);
99
}
else
{
100
bubble_sort_with_permutation
(v,
p
,
n
);
101
}
102
}
103
104
}
// namespace rheolef
105
#endif // _RHEOLEF_MSG_SORT_WITH_PERMUTATION_H
rheolef::bubble_sort_with_permutation
void bubble_sort_with_permutation(RandomIterator v, SizeRandomIterator p, Size n)
Definition:
msg_sort_with_permutation.h:74
rheolef::quick_sort_with_permutation
void quick_sort_with_permutation(RandomIterator v, SizeRandomIterator p, Size start, Size end)
Definition:
msg_sort_with_permutation.h:42
p
Definition:
sphere.icc:25
rheolef::sort_with_permutation
void sort_with_permutation(RandomIterator v, SizeRandomIterator p, Size n)
Definition:
msg_sort_with_permutation.h:91
rheolef
This file is part of Rheolef.
Definition:
compiler_eigen.h:37
mkgeo_ball.n
n
Definition:
mkgeo_ball.sh:150
T
Expr1::float_type T
Definition:
field_expr.h:218