Actual source code: sortip.c
petsc-3.14.6 2021-03-30
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) {t=a;a=b;b=t;}
13: static PetscErrorCode PetscSortIntWithPermutation_Private(const PetscInt v[],PetscInt vdx[],PetscInt right)
14: {
16: PetscInt tmp,i,vl,last;
19: if (right <= 1) {
20: if (right == 1) {
21: if (v[vdx[0]] > v[vdx[1]]) SWAP(vdx[0],vdx[1],tmp);
22: }
23: return(0);
24: }
25: SWAP(vdx[0],vdx[right/2],tmp);
26: vl = v[vdx[0]];
27: last = 0;
28: for (i=1; i<=right; i++) {
29: if (v[vdx[i]] < vl) {last++; SWAP(vdx[last],vdx[i],tmp);}
30: }
31: SWAP(vdx[0],vdx[last],tmp);
32: PetscSortIntWithPermutation_Private(v,vdx,last-1);
33: PetscSortIntWithPermutation_Private(v,vdx+last+1,right-(last+1));
34: return(0);
35: }
37: /*@
38: PetscSortIntWithPermutation - Computes the permutation of values that gives
39: a sorted sequence.
41: Not Collective
43: Input Parameters:
44: + n - number of values to sort
45: . i - values to sort
46: - idx - permutation array. Must be initialized to 0:n-1 on input.
48: Level: intermediate
50: Notes:
51: On output i is unchanged and idx[i] is the position of the i-th smallest index in i.
53: .seealso: PetscSortInt(), PetscSortRealWithPermutation(), PetscSortIntWithArray()
54: @*/
55: PetscErrorCode PetscSortIntWithPermutation(PetscInt n,const PetscInt i[],PetscInt idx[])
56: {
58: PetscInt j,k,tmp,ik;
61: if (n<8) {
62: for (k=0; k<n; k++) {
63: ik = i[idx[k]];
64: for (j=k+1; j<n; j++) {
65: if (ik > i[idx[j]]) {
66: SWAP(idx[k],idx[j],tmp);
67: ik = i[idx[k]];
68: }
69: }
70: }
71: } else {
72: PetscSortIntWithPermutation_Private(i,idx,n-1);
73: }
74: return(0);
75: }
77: /* ---------------------------------------------------------------------- */
79: static PetscErrorCode PetscSortRealWithPermutation_Private(const PetscReal v[],PetscInt vdx[],PetscInt right)
80: {
81: PetscReal vl;
83: PetscInt tmp,i,last;
86: if (right <= 1) {
87: if (right == 1) {
88: if (v[vdx[0]] > v[vdx[1]]) SWAP(vdx[0],vdx[1],tmp);
89: }
90: return(0);
91: }
92: SWAP(vdx[0],vdx[right/2],tmp);
93: vl = v[vdx[0]];
94: last = 0;
95: for (i=1; i<=right; i++) {
96: if (v[vdx[i]] < vl) {last++; SWAP(vdx[last],vdx[i],tmp);}
97: }
98: SWAP(vdx[0],vdx[last],tmp);
99: PetscSortRealWithPermutation_Private(v,vdx,last-1);
100: PetscSortRealWithPermutation_Private(v,vdx+last+1,right-(last+1));
101: return(0);
102: }
104: /*@
105: PetscSortRealWithPermutation - Computes the permutation of values that gives
106: a sorted sequence.
108: Not Collective
110: Input Parameters:
111: + n - number of values to sort
112: . i - values to sort
113: - idx - permutation array. Must be initialized to 0:n-1 on input.
115: Level: intermediate
117: Notes:
118: i is unchanged on output.
120: .seealso: PetscSortReal(), PetscSortIntWithPermutation()
121: @*/
122: PetscErrorCode PetscSortRealWithPermutation(PetscInt n,const PetscReal i[],PetscInt idx[])
123: {
125: PetscInt j,k,tmp;
126: PetscReal ik;
129: if (n<8) {
130: for (k=0; k<n; k++) {
131: ik = i[idx[k]];
132: for (j=k+1; j<n; j++) {
133: if (ik > i[idx[j]]) {
134: SWAP(idx[k],idx[j],tmp);
135: ik = i[idx[k]];
136: }
137: }
138: }
139: } else {
140: PetscSortRealWithPermutation_Private(i,idx,n-1);
141: }
142: return(0);
143: }
145: static PetscErrorCode PetscSortStrWithPermutation_Private(const char* v[],PetscInt vdx[],PetscInt right)
146: {
148: PetscInt tmp,i,last;
149: PetscBool gt;
150: const char *vl;
153: if (right <= 1) {
154: if (right == 1) {
155: PetscStrgrt(v[vdx[0]],v[vdx[1]],>);
156: if (gt) SWAP(vdx[0],vdx[1],tmp);
157: }
158: return(0);
159: }
160: SWAP(vdx[0],vdx[right/2],tmp);
161: vl = v[vdx[0]];
162: last = 0;
163: for (i=1; i<=right; i++) {
164: PetscStrgrt(vl,v[vdx[i]],>);
165: if (gt) {last++; SWAP(vdx[last],vdx[i],tmp);}
166: }
167: SWAP(vdx[0],vdx[last],tmp);
168: PetscSortStrWithPermutation_Private(v,vdx,last-1);
169: PetscSortStrWithPermutation_Private(v,vdx+last+1,right-(last+1));
170: return(0);
171: }
173: /*@C
174: PetscSortStrWithPermutation - Computes the permutation of values that gives
175: a sorted sequence.
177: Not Collective
179: Input Parameters:
180: + n - number of values to sort
181: . i - values to sort
182: - idx - permutation array. Must be initialized to 0:n-1 on input.
184: Level: intermediate
186: Notes:
187: i is unchanged on output.
189: .seealso: PetscSortInt(), PetscSortRealWithPermutation()
190: @*/
191: PetscErrorCode PetscSortStrWithPermutation(PetscInt n,const char* i[],PetscInt idx[])
192: {
194: PetscInt j,k,tmp;
195: const char *ik;
196: PetscBool gt;
199: if (n<8) {
200: for (k=0; k<n; k++) {
201: ik = i[idx[k]];
202: for (j=k+1; j<n; j++) {
203: PetscStrgrt(ik,i[idx[j]],>);
204: if (gt) {
205: SWAP(idx[k],idx[j],tmp);
206: ik = i[idx[k]];
207: }
208: }
209: }
210: } else {
211: PetscSortStrWithPermutation_Private(i,idx,n-1);
212: }
213: return(0);
214: }