Actual source code: sortip.c
2: /*
3: This file contains routines for sorting integers and doubles with a permutation array.
5: The word "register" in this code is used to identify data that is not
6: aliased. For some compilers, this can cause the compiler to fail to
7: place inner-loop variables into registers.
8: */
9: #include <petscsys.h>
11: #define SWAP(a, b, t) \
12: { \
13: t = a; \
14: a = b; \
15: b = t; \
16: }
18: static PetscErrorCode PetscSortIntWithPermutation_Private(const PetscInt v[], PetscInt vdx[], PetscInt right)
19: {
20: PetscInt tmp, i, vl, last;
22: if (right <= 1) {
23: if (right == 1) {
24: if (v[vdx[0]] > v[vdx[1]]) SWAP(vdx[0], vdx[1], tmp);
25: }
26: return 0;
27: }
28: SWAP(vdx[0], vdx[right / 2], tmp);
29: vl = v[vdx[0]];
30: last = 0;
31: for (i = 1; i <= right; i++) {
32: if (v[vdx[i]] < vl) {
33: last++;
34: SWAP(vdx[last], vdx[i], tmp);
35: }
36: }
37: SWAP(vdx[0], vdx[last], tmp);
38: PetscSortIntWithPermutation_Private(v, vdx, last - 1);
39: PetscSortIntWithPermutation_Private(v, vdx + last + 1, right - (last + 1));
40: return 0;
41: }
43: /*@
44: PetscSortIntWithPermutation - Computes the permutation of `PetscInt` that gives
45: a sorted sequence.
47: Not Collective
49: Input Parameters:
50: + n - number of values to sort
51: . i - values to sort
52: - idx - permutation array. Must be initialized to 0:n-1 on input.
54: Level: intermediate
56: Note:
57: On output i is unchanged and idx[i] is the position of the i-th smallest index in i.
59: .seealso: `PetscSortInt()`, `PetscSortRealWithPermutation()`, `PetscSortIntWithArray()`
60: @*/
61: PetscErrorCode PetscSortIntWithPermutation(PetscInt n, const PetscInt i[], PetscInt idx[])
62: {
63: PetscInt j, k, tmp, ik;
65: if (n < 8) {
66: for (k = 0; k < n; k++) {
67: ik = i[idx[k]];
68: for (j = k + 1; j < n; j++) {
69: if (ik > i[idx[j]]) {
70: SWAP(idx[k], idx[j], tmp);
71: ik = i[idx[k]];
72: }
73: }
74: }
75: } else {
76: PetscSortIntWithPermutation_Private(i, idx, n - 1);
77: }
78: return 0;
79: }
81: /* ---------------------------------------------------------------------- */
83: static PetscErrorCode PetscSortRealWithPermutation_Private(const PetscReal v[], PetscInt vdx[], PetscInt right)
84: {
85: PetscReal vl;
86: PetscInt tmp, i, last;
88: if (right <= 1) {
89: if (right == 1) {
90: if (v[vdx[0]] > v[vdx[1]]) SWAP(vdx[0], vdx[1], tmp);
91: }
92: return 0;
93: }
94: SWAP(vdx[0], vdx[right / 2], tmp);
95: vl = v[vdx[0]];
96: last = 0;
97: for (i = 1; i <= right; i++) {
98: if (v[vdx[i]] < vl) {
99: last++;
100: SWAP(vdx[last], vdx[i], tmp);
101: }
102: }
103: SWAP(vdx[0], vdx[last], tmp);
104: PetscSortRealWithPermutation_Private(v, vdx, last - 1);
105: PetscSortRealWithPermutation_Private(v, vdx + last + 1, right - (last + 1));
106: return 0;
107: }
109: /*@
110: PetscSortRealWithPermutation - Computes the permutation of `PetscReal` that gives
111: a sorted sequence.
113: Not Collective
115: Input Parameters:
116: + n - number of values to sort
117: . i - values to sort
118: - idx - permutation array. Must be initialized to 0:n-1 on input.
120: Level: intermediate
122: Note:
123: i is unchanged on output.
125: .seealso: `PetscSortReal()`, `PetscSortIntWithPermutation()`
126: @*/
127: PetscErrorCode PetscSortRealWithPermutation(PetscInt n, const PetscReal i[], PetscInt idx[])
128: {
129: PetscInt j, k, tmp;
130: PetscReal ik;
132: if (n < 8) {
133: for (k = 0; k < n; k++) {
134: ik = i[idx[k]];
135: for (j = k + 1; j < n; j++) {
136: if (ik > i[idx[j]]) {
137: SWAP(idx[k], idx[j], tmp);
138: ik = i[idx[k]];
139: }
140: }
141: }
142: } else {
143: PetscSortRealWithPermutation_Private(i, idx, n - 1);
144: }
145: return 0;
146: }
148: static PetscErrorCode PetscSortStrWithPermutation_Private(const char *v[], PetscInt vdx[], PetscInt right)
149: {
150: PetscInt tmp, i, last;
151: PetscBool gt;
152: const char *vl;
154: if (right <= 1) {
155: if (right == 1) {
156: PetscStrgrt(v[vdx[0]], v[vdx[1]], >);
157: if (gt) SWAP(vdx[0], vdx[1], tmp);
158: }
159: return 0;
160: }
161: SWAP(vdx[0], vdx[right / 2], tmp);
162: vl = v[vdx[0]];
163: last = 0;
164: for (i = 1; i <= right; i++) {
165: PetscStrgrt(vl, v[vdx[i]], >);
166: if (gt) {
167: last++;
168: SWAP(vdx[last], vdx[i], tmp);
169: }
170: }
171: SWAP(vdx[0], vdx[last], tmp);
172: PetscSortStrWithPermutation_Private(v, vdx, last - 1);
173: PetscSortStrWithPermutation_Private(v, vdx + last + 1, right - (last + 1));
174: return 0;
175: }
177: /*@C
178: PetscSortStrWithPermutation - Computes the permutation of strings that gives
179: a sorted sequence.
181: Not Collective
183: Input Parameters:
184: + n - number of values to sort
185: . i - values to sort
186: - idx - permutation array. Must be initialized to 0:n-1 on input.
188: Level: intermediate
190: Note:
191: i is unchanged on output.
193: .seealso: `PetscSortInt()`, `PetscSortRealWithPermutation()`
194: @*/
195: PetscErrorCode PetscSortStrWithPermutation(PetscInt n, const char *i[], PetscInt idx[])
196: {
197: PetscInt j, k, tmp;
198: const char *ik;
199: PetscBool gt;
201: if (n < 8) {
202: for (k = 0; k < n; k++) {
203: ik = i[idx[k]];
204: for (j = k + 1; j < n; j++) {
205: PetscStrgrt(ik, i[idx[j]], >);
206: if (gt) {
207: SWAP(idx[k], idx[j], tmp);
208: ik = i[idx[k]];
209: }
210: }
211: }
212: } else {
213: PetscSortStrWithPermutation_Private(i, idx, n - 1);
214: }
215: return 0;
216: }