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) {t=a;a=b;b=t;}
13: static PetscErrorCode PetscSortIntWithPermutation_Private(const PetscInt v[],PetscInt vdx[],PetscInt right)
14: {
15: PetscInt tmp,i,vl,last;
17: if (right <= 1) {
18: if (right == 1) {
19: if (v[vdx[0]] > v[vdx[1]]) SWAP(vdx[0],vdx[1],tmp);
20: }
21: return 0;
22: }
23: SWAP(vdx[0],vdx[right/2],tmp);
24: vl = v[vdx[0]];
25: last = 0;
26: for (i=1; i<=right; i++) {
27: if (v[vdx[i]] < vl) {last++; SWAP(vdx[last],vdx[i],tmp);}
28: }
29: SWAP(vdx[0],vdx[last],tmp);
30: PetscSortIntWithPermutation_Private(v,vdx,last-1);
31: PetscSortIntWithPermutation_Private(v,vdx+last+1,right-(last+1));
32: return 0;
33: }
35: /*@
36: PetscSortIntWithPermutation - Computes the permutation of values that gives
37: a sorted sequence.
39: Not Collective
41: Input Parameters:
42: + n - number of values to sort
43: . i - values to sort
44: - idx - permutation array. Must be initialized to 0:n-1 on input.
46: Level: intermediate
48: Notes:
49: On output i is unchanged and idx[i] is the position of the i-th smallest index in i.
51: .seealso: PetscSortInt(), PetscSortRealWithPermutation(), PetscSortIntWithArray()
52: @*/
53: PetscErrorCode PetscSortIntWithPermutation(PetscInt n,const PetscInt i[],PetscInt idx[])
54: {
55: PetscInt j,k,tmp,ik;
57: if (n<8) {
58: for (k=0; k<n; k++) {
59: ik = i[idx[k]];
60: for (j=k+1; j<n; j++) {
61: if (ik > i[idx[j]]) {
62: SWAP(idx[k],idx[j],tmp);
63: ik = i[idx[k]];
64: }
65: }
66: }
67: } else {
68: PetscSortIntWithPermutation_Private(i,idx,n-1);
69: }
70: return 0;
71: }
73: /* ---------------------------------------------------------------------- */
75: static PetscErrorCode PetscSortRealWithPermutation_Private(const PetscReal v[],PetscInt vdx[],PetscInt right)
76: {
77: PetscReal vl;
78: PetscInt tmp,i,last;
80: if (right <= 1) {
81: if (right == 1) {
82: if (v[vdx[0]] > v[vdx[1]]) SWAP(vdx[0],vdx[1],tmp);
83: }
84: return 0;
85: }
86: SWAP(vdx[0],vdx[right/2],tmp);
87: vl = v[vdx[0]];
88: last = 0;
89: for (i=1; i<=right; i++) {
90: if (v[vdx[i]] < vl) {last++; SWAP(vdx[last],vdx[i],tmp);}
91: }
92: SWAP(vdx[0],vdx[last],tmp);
93: PetscSortRealWithPermutation_Private(v,vdx,last-1);
94: PetscSortRealWithPermutation_Private(v,vdx+last+1,right-(last+1));
95: return 0;
96: }
98: /*@
99: PetscSortRealWithPermutation - Computes the permutation of values that gives
100: a sorted sequence.
102: Not Collective
104: Input Parameters:
105: + n - number of values to sort
106: . i - values to sort
107: - idx - permutation array. Must be initialized to 0:n-1 on input.
109: Level: intermediate
111: Notes:
112: i is unchanged on output.
114: .seealso: PetscSortReal(), PetscSortIntWithPermutation()
115: @*/
116: PetscErrorCode PetscSortRealWithPermutation(PetscInt n,const PetscReal i[],PetscInt idx[])
117: {
118: PetscInt j,k,tmp;
119: PetscReal ik;
121: if (n<8) {
122: for (k=0; k<n; k++) {
123: ik = i[idx[k]];
124: for (j=k+1; j<n; j++) {
125: if (ik > i[idx[j]]) {
126: SWAP(idx[k],idx[j],tmp);
127: ik = i[idx[k]];
128: }
129: }
130: }
131: } else {
132: PetscSortRealWithPermutation_Private(i,idx,n-1);
133: }
134: return 0;
135: }
137: static PetscErrorCode PetscSortStrWithPermutation_Private(const char* v[],PetscInt vdx[],PetscInt right)
138: {
139: PetscInt tmp,i,last;
140: PetscBool gt;
141: const char *vl;
143: if (right <= 1) {
144: if (right == 1) {
145: PetscStrgrt(v[vdx[0]],v[vdx[1]],>);
146: if (gt) SWAP(vdx[0],vdx[1],tmp);
147: }
148: return 0;
149: }
150: SWAP(vdx[0],vdx[right/2],tmp);
151: vl = v[vdx[0]];
152: last = 0;
153: for (i=1; i<=right; i++) {
154: PetscStrgrt(vl,v[vdx[i]],>);
155: if (gt) {last++; SWAP(vdx[last],vdx[i],tmp);}
156: }
157: SWAP(vdx[0],vdx[last],tmp);
158: PetscSortStrWithPermutation_Private(v,vdx,last-1);
159: PetscSortStrWithPermutation_Private(v,vdx+last+1,right-(last+1));
160: return 0;
161: }
163: /*@C
164: PetscSortStrWithPermutation - Computes the permutation of values that gives
165: a sorted sequence.
167: Not Collective
169: Input Parameters:
170: + n - number of values to sort
171: . i - values to sort
172: - idx - permutation array. Must be initialized to 0:n-1 on input.
174: Level: intermediate
176: Notes:
177: i is unchanged on output.
179: .seealso: PetscSortInt(), PetscSortRealWithPermutation()
180: @*/
181: PetscErrorCode PetscSortStrWithPermutation(PetscInt n,const char* i[],PetscInt idx[])
182: {
183: PetscInt j,k,tmp;
184: const char *ik;
185: PetscBool gt;
187: if (n<8) {
188: for (k=0; k<n; k++) {
189: ik = i[idx[k]];
190: for (j=k+1; j<n; j++) {
191: PetscStrgrt(ik,i[idx[j]],>);
192: if (gt) {
193: SWAP(idx[k],idx[j],tmp);
194: ik = i[idx[k]];
195: }
196: }
197: }
198: } else {
199: PetscSortStrWithPermutation_Private(i,idx,n-1);
200: }
201: return 0;
202: }