Rheolef  7.2
an efficient C++ finite element environment
 
Loading...
Searching...
No Matches
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
23/*
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"
38namespace rheolef {
39
40template<class RandomIterator, class SizeRandomIterator, class Size>
41void
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}
72template<class RandomIterator, class SizeRandomIterator, class Size>
73void
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}
89template<class RandomIterator, class SizeRandomIterator, class Size>
90void
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 {
101 }
102}
103
104} // namespace rheolef
105#endif // _RHEOLEF_MSG_SORT_WITH_PERMUTATION_H
Expr1::float_type T
Definition field_expr.h:230
This file is part of Rheolef.
void sort_with_permutation(RandomIterator v, SizeRandomIterator p, Size n)
void quick_sort_with_permutation(RandomIterator v, SizeRandomIterator p, Size start, Size end)
void bubble_sort_with_permutation(RandomIterator v, SizeRandomIterator p, Size n)
Definition sphere.icc:25