Actual source code: sorti.c

1: #define PETSC_DLL
2: /*
3:    This file contains routines for sorting integers. Values are sorted in place.

6:    The word "register"  in this code is used to identify data that is not
7:    aliased.  For some compilers, marking variables as register can improve
8:    the compiler optimizations.
9:  */
10:  #include petsc.h
11:  #include petscsys.h

13: #define SWAP(a,b,t) {t=a;a=b;b=t;}

15: /* -----------------------------------------------------------------------*/

19: /*
20:    A simple version of quicksort; taken from Kernighan and Ritchie, page 87.
21:    Assumes 0 origin for v, number of elements = right+1 (right is index of
22:    right-most member).
23: */
24: static PetscErrorCode PetscSortInt_Private(PetscInt *v,PetscInt right)
25: {
27:   PetscInt i,vl,last,tmp;

30:   if (right <= 1) {
31:     if (right == 1) {
32:       if (v[0] > v[1]) SWAP(v[0],v[1],tmp);
33:     }
34:     return(0);
35:   }
36:   SWAP(v[0],v[right/2],tmp);
37:   vl   = v[0];
38:   last = 0;
39:   for (i=1; i<=right; i++) {
40:     if (v[i] < vl) {last++; SWAP(v[last],v[i],tmp);}
41:   }
42:   SWAP(v[0],v[last],tmp);
43:   PetscSortInt_Private(v,last-1);
44:   PetscSortInt_Private(v+last+1,right-(last+1));
45:   return(0);
46: }

50: /*@
51:    PetscSortInt - Sorts an array of integers in place in increasing order.

53:    Not Collective

55:    Input Parameters:
56: +  n  - number of values
57: -  i  - array of integers

59:    Level: intermediate

61:    Concepts: sorting^ints

63: .seealso: PetscSortReal(), PetscSortIntWithPermutation()
64: @*/
65: PetscErrorCode  PetscSortInt(PetscInt n,PetscInt i[])
66: {
68:   PetscInt j,k,tmp,ik;

71:   if (n<8) {
72:     for (k=0; k<n; k++) {
73:       ik = i[k];
74:       for (j=k+1; j<n; j++) {
75:         if (ik > i[j]) {
76:           SWAP(i[k],i[j],tmp);
77:           ik = i[k];
78:         }
79:       }
80:     }
81:   } else {
82:     PetscSortInt_Private(i,n-1);
83:   }
84:   return(0);
85: }

87: /* -----------------------------------------------------------------------*/
88: #define SWAP2(a,b,c,d,t) {t=a;a=b;b=t;t=c;c=d;d=t;}

92: /*
93:    A simple version of quicksort; taken from Kernighan and Ritchie, page 87.
94:    Assumes 0 origin for v, number of elements = right+1 (right is index of
95:    right-most member).
96: */
97: static PetscErrorCode PetscSortIntWithArray_Private(PetscInt *v,PetscInt *V,PetscInt right)
98: {
100:   PetscInt i,vl,last,tmp;

103:   if (right <= 1) {
104:     if (right == 1) {
105:       if (v[0] > v[1]) SWAP2(v[0],v[1],V[0],V[1],tmp);
106:     }
107:     return(0);
108:   }
109:   SWAP2(v[0],v[right/2],V[0],V[right/2],tmp);
110:   vl   = v[0];
111:   last = 0;
112:   for (i=1; i<=right; i++) {
113:     if (v[i] < vl) {last++; SWAP2(v[last],v[i],V[last],V[i],tmp);}
114:   }
115:   SWAP2(v[0],v[last],V[0],V[last],tmp);
116:   PetscSortIntWithArray_Private(v,V,last-1);
117:   PetscSortIntWithArray_Private(v+last+1,V+last+1,right-(last+1));
118:   return(0);
119: }

123: /*@
124:    PetscSortIntWithArray - Sorts an array of integers in place in increasing order;
125:        changes a second array to match the sorted first array.

127:    Not Collective

129:    Input Parameters:
130: +  n  - number of values
131: .  i  - array of integers
132: -  I - second array of integers

134:    Level: intermediate

136:    Concepts: sorting^ints with array

138: .seealso: PetscSortReal(), PetscSortIntPermutation(), PetscSortInt()
139: @*/
140: PetscErrorCode  PetscSortIntWithArray(PetscInt n,PetscInt i[],PetscInt Ii[])
141: {
143:   PetscInt j,k,tmp,ik;

146:   if (n<8) {
147:     for (k=0; k<n; k++) {
148:       ik = i[k];
149:       for (j=k+1; j<n; j++) {
150:         if (ik > i[j]) {
151:           SWAP2(i[k],i[j],Ii[k],Ii[j],tmp);
152:           ik = i[k];
153:         }
154:       }
155:     }
156:   } else {
157:     PetscSortIntWithArray_Private(i,Ii,n-1);
158:   }
159:   return(0);
160: }

162: /* -----------------------------------------------------------------------*/
163: #define SWAP2IntScalar(a,b,c,d,t,ts) {t=a;a=b;b=t;ts=c;c=d;d=ts;}

167: /*
168:    Modified from PetscSortIntWithArray_Private().
169: */
170: static PetscErrorCode PetscSortIntWithScalarArray_Private(PetscInt *v,PetscScalar *V,PetscInt right)
171: {
173:   PetscInt       i,vl,last,tmp;
174:   PetscScalar    stmp;

177:   if (right <= 1) {
178:     if (right == 1) {
179:       if (v[0] > v[1]) SWAP2IntScalar(v[0],v[1],V[0],V[1],tmp,stmp);
180:     }
181:     return(0);
182:   }
183:   SWAP2IntScalar(v[0],v[right/2],V[0],V[right/2],tmp,stmp);
184:   vl   = v[0];
185:   last = 0;
186:   for (i=1; i<=right; i++) {
187:     if (v[i] < vl) {last++; SWAP2IntScalar(v[last],v[i],V[last],V[i],tmp,stmp);}
188:   }
189:   SWAP2IntScalar(v[0],v[last],V[0],V[last],tmp,stmp);
190:   PetscSortIntWithScalarArray_Private(v,V,last-1);
191:   PetscSortIntWithScalarArray_Private(v+last+1,V+last+1,right-(last+1));
192:   return(0);
193: }

197: /*@
198:    PetscSortIntWithScalarArray - Sorts an array of integers in place in increasing order;
199:        changes a second SCALAR array to match the sorted first INTEGER array.

201:    Not Collective

203:    Input Parameters:
204: +  n  - number of values
205: .  i  - array of integers
206: -  I - second array of scalars

208:    Level: intermediate

210:    Concepts: sorting^ints with array

212: .seealso: PetscSortReal(), PetscSortIntPermutation(), PetscSortInt(), PetscSortIntWithArray()
213: @*/
214: PetscErrorCode  PetscSortIntWithScalarArray(PetscInt n,PetscInt i[],PetscScalar Ii[])
215: {
217:   PetscInt       j,k,tmp,ik;
218:   PetscScalar    stmp;

221:   if (n<8) {
222:     for (k=0; k<n; k++) {
223:       ik = i[k];
224:       for (j=k+1; j<n; j++) {
225:         if (ik > i[j]) {
226:           SWAP2IntScalar(i[k],i[j],Ii[k],Ii[j],tmp,stmp);
227:           ik = i[k];
228:         }
229:       }
230:     }
231:   } else {
232:     PetscSortIntWithScalarArray_Private(i,Ii,n-1);
233:   }
234:   return(0);
235: }