Actual source code: sortip.c
petsc-3.6.1 2015-08-06
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> /*I "petscsys.h" I*/
11: #define SWAP(a,b,t) {t=a;a=b;b=t;}
15: static PetscErrorCode PetscSortIntWithPermutation_Private(const PetscInt v[],PetscInt vdx[],PetscInt right)
16: {
18: PetscInt tmp,i,vl,last;
21: if (right <= 1) {
22: if (right == 1) {
23: if (v[vdx[0]] > v[vdx[1]]) SWAP(vdx[0],vdx[1],tmp);
24: }
25: return(0);
26: }
27: SWAP(vdx[0],vdx[right/2],tmp);
28: vl = v[vdx[0]];
29: last = 0;
30: for (i=1; i<=right; i++) {
31: if (v[vdx[i]] < vl) {last++; SWAP(vdx[last],vdx[i],tmp);}
32: }
33: SWAP(vdx[0],vdx[last],tmp);
34: PetscSortIntWithPermutation_Private(v,vdx,last-1);
35: PetscSortIntWithPermutation_Private(v,vdx+last+1,right-(last+1));
36: return(0);
37: }
41: /*@
42: PetscSortIntWithPermutation - Computes the permutation of values that gives
43: a sorted sequence.
45: Not Collective
47: Input Parameters:
48: + n - number of values to sort
49: . i - values to sort
50: - idx - permutation array. Must be initialized to 0:n-1 on input.
52: Level: intermediate
54: Notes:
55: On output i is unchanged and idx[i] is the position of the i-th smallest index in i.
57: Concepts: sorting^ints with permutation
59: .seealso: PetscSortInt(), PetscSortRealWithPermutation(), PetscSortIntWithArray()
60: @*/
61: PetscErrorCode PetscSortIntWithPermutation(PetscInt n,const PetscInt i[],PetscInt idx[])
62: {
64: PetscInt j,k,tmp,ik;
67: if (n<8) {
68: for (k=0; k<n; k++) {
69: ik = i[idx[k]];
70: for (j=k+1; j<n; j++) {
71: if (ik > i[idx[j]]) {
72: SWAP(idx[k],idx[j],tmp);
73: ik = i[idx[k]];
74: }
75: }
76: }
77: } else {
78: PetscSortIntWithPermutation_Private(i,idx,n-1);
79: }
80: return(0);
81: }
83: /* ---------------------------------------------------------------------- */
87: static PetscErrorCode PetscSortRealWithPermutation_Private(const PetscReal v[],PetscInt vdx[],PetscInt right)
88: {
89: PetscReal vl;
91: PetscInt tmp,i,last;
94: if (right <= 1) {
95: if (right == 1) {
96: if (v[vdx[0]] > v[vdx[1]]) SWAP(vdx[0],vdx[1],tmp);
97: }
98: return(0);
99: }
100: SWAP(vdx[0],vdx[right/2],tmp);
101: vl = v[vdx[0]];
102: last = 0;
103: for (i=1; i<=right; i++) {
104: if (v[vdx[i]] < vl) {last++; SWAP(vdx[last],vdx[i],tmp);}
105: }
106: SWAP(vdx[0],vdx[last],tmp);
107: PetscSortRealWithPermutation_Private(v,vdx,last-1);
108: PetscSortRealWithPermutation_Private(v,vdx+last+1,right-(last+1));
109: return(0);
110: }
114: /*@
115: PetscSortRealWithPermutation - Computes the permutation of values that gives
116: a sorted sequence.
118: Not Collective
120: Input Parameters:
121: + n - number of values to sort
122: . i - values to sort
123: - idx - permutation array. Must be initialized to 0:n-1 on input.
125: Level: intermediate
127: Notes:
128: i is unchanged on output.
130: Concepts: sorting^doubles with permutation
132: .seealso: PetscSortReal(), PetscSortIntWithPermutation()
133: @*/
134: PetscErrorCode PetscSortRealWithPermutation(PetscInt n,const PetscReal i[],PetscInt idx[])
135: {
137: PetscInt j,k,tmp;
138: PetscReal ik;
141: if (n<8) {
142: for (k=0; k<n; k++) {
143: ik = i[idx[k]];
144: for (j=k+1; j<n; j++) {
145: if (ik > i[idx[j]]) {
146: SWAP(idx[k],idx[j],tmp);
147: ik = i[idx[k]];
148: }
149: }
150: }
151: } else {
152: PetscSortRealWithPermutation_Private(i,idx,n-1);
153: }
154: return(0);
155: }
159: static PetscErrorCode PetscSortStrWithPermutation_Private(const char* v[],PetscInt vdx[],PetscInt right)
160: {
162: PetscInt tmp,i,last;
163: PetscBool gt;
164: const char *vl;
167: if (right <= 1) {
168: if (right == 1) {
169: PetscStrgrt(v[vdx[0]],v[vdx[1]],>);
170: if (gt) SWAP(vdx[0],vdx[1],tmp);
171: }
172: return(0);
173: }
174: SWAP(vdx[0],vdx[right/2],tmp);
175: vl = v[vdx[0]];
176: last = 0;
177: for (i=1; i<=right; i++) {
178: PetscStrgrt(vl,v[vdx[i]],>);
179: if (gt) {last++; SWAP(vdx[last],vdx[i],tmp);}
180: }
181: SWAP(vdx[0],vdx[last],tmp);
182: PetscSortStrWithPermutation_Private(v,vdx,last-1);
183: PetscSortStrWithPermutation_Private(v,vdx+last+1,right-(last+1));
184: return(0);
185: }
189: /*@C
190: PetscSortStrWithPermutation - Computes the permutation of values that gives
191: a sorted sequence.
193: Not Collective
195: Input Parameters:
196: + n - number of values to sort
197: . i - values to sort
198: - idx - permutation array. Must be initialized to 0:n-1 on input.
200: Level: intermediate
202: Notes:
203: i is unchanged on output.
205: Concepts: sorting^ints with permutation
207: .seealso: PetscSortInt(), PetscSortRealWithPermutation()
208: @*/
209: PetscErrorCode PetscSortStrWithPermutation(PetscInt n,const char* i[],PetscInt idx[])
210: {
212: PetscInt j,k,tmp;
213: const char *ik;
214: PetscBool gt;
217: if (n<8) {
218: for (k=0; k<n; k++) {
219: ik = i[idx[k]];
220: for (j=k+1; j<n; j++) {
221: PetscStrgrt(ik,i[idx[j]],>);
222: if (gt) {
223: SWAP(idx[k],idx[j],tmp);
224: ik = i[idx[k]];
225: }
226: }
227: }
228: } else {
229: PetscSortStrWithPermutation_Private(i,idx,n-1);
230: }
231: return(0);
232: }