Actual source code: sortip.c
petsc-3.11.4 2019-09-28
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: Concepts: sorting^ints with permutation
55: .seealso: PetscSortInt(), PetscSortRealWithPermutation(), PetscSortIntWithArray()
56: @*/
57: PetscErrorCode PetscSortIntWithPermutation(PetscInt n,const PetscInt i[],PetscInt idx[])
58: {
60: PetscInt j,k,tmp,ik;
63: if (n<8) {
64: for (k=0; k<n; k++) {
65: ik = i[idx[k]];
66: for (j=k+1; j<n; j++) {
67: if (ik > i[idx[j]]) {
68: SWAP(idx[k],idx[j],tmp);
69: ik = i[idx[k]];
70: }
71: }
72: }
73: } else {
74: PetscSortIntWithPermutation_Private(i,idx,n-1);
75: }
76: return(0);
77: }
79: /* ---------------------------------------------------------------------- */
81: static PetscErrorCode PetscSortRealWithPermutation_Private(const PetscReal v[],PetscInt vdx[],PetscInt right)
82: {
83: PetscReal vl;
85: 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) {last++; SWAP(vdx[last],vdx[i],tmp);}
99: }
100: SWAP(vdx[0],vdx[last],tmp);
101: PetscSortRealWithPermutation_Private(v,vdx,last-1);
102: PetscSortRealWithPermutation_Private(v,vdx+last+1,right-(last+1));
103: return(0);
104: }
106: /*@
107: PetscSortRealWithPermutation - Computes the permutation of values that gives
108: a sorted sequence.
110: Not Collective
112: Input Parameters:
113: + n - number of values to sort
114: . i - values to sort
115: - idx - permutation array. Must be initialized to 0:n-1 on input.
117: Level: intermediate
119: Notes:
120: i is unchanged on output.
122: Concepts: sorting^doubles with permutation
124: .seealso: PetscSortReal(), PetscSortIntWithPermutation()
125: @*/
126: PetscErrorCode PetscSortRealWithPermutation(PetscInt n,const PetscReal i[],PetscInt idx[])
127: {
129: PetscInt j,k,tmp;
130: PetscReal ik;
133: if (n<8) {
134: for (k=0; k<n; k++) {
135: ik = i[idx[k]];
136: for (j=k+1; j<n; j++) {
137: if (ik > i[idx[j]]) {
138: SWAP(idx[k],idx[j],tmp);
139: ik = i[idx[k]];
140: }
141: }
142: }
143: } else {
144: PetscSortRealWithPermutation_Private(i,idx,n-1);
145: }
146: return(0);
147: }
149: static PetscErrorCode PetscSortStrWithPermutation_Private(const char* v[],PetscInt vdx[],PetscInt right)
150: {
152: PetscInt tmp,i,last;
153: PetscBool gt;
154: const char *vl;
157: if (right <= 1) {
158: if (right == 1) {
159: PetscStrgrt(v[vdx[0]],v[vdx[1]],>);
160: if (gt) SWAP(vdx[0],vdx[1],tmp);
161: }
162: return(0);
163: }
164: SWAP(vdx[0],vdx[right/2],tmp);
165: vl = v[vdx[0]];
166: last = 0;
167: for (i=1; i<=right; i++) {
168: PetscStrgrt(vl,v[vdx[i]],>);
169: if (gt) {last++; SWAP(vdx[last],vdx[i],tmp);}
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 values 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: Notes:
191: i is unchanged on output.
193: Concepts: sorting^ints with permutation
195: .seealso: PetscSortInt(), PetscSortRealWithPermutation()
196: @*/
197: PetscErrorCode PetscSortStrWithPermutation(PetscInt n,const char* i[],PetscInt idx[])
198: {
200: PetscInt j,k,tmp;
201: const char *ik;
202: PetscBool gt;
205: if (n<8) {
206: for (k=0; k<n; k++) {
207: ik = i[idx[k]];
208: for (j=k+1; j<n; j++) {
209: PetscStrgrt(ik,i[idx[j]],>);
210: if (gt) {
211: SWAP(idx[k],idx[j],tmp);
212: ik = i[idx[k]];
213: }
214: }
215: }
216: } else {
217: PetscSortStrWithPermutation_Private(i,idx,n-1);
218: }
219: return(0);
220: }