1 2 /* 3 This file contains routines for sorting integers and doubles with a permutation array. 4 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*/ 10 11 #define SWAP(a,b,t) {t=a;a=b;b=t;} 12 13 static PetscErrorCode PetscSortIntWithPermutation_Private(const PetscInt v[],PetscInt vdx[],PetscInt right) 14 { 15 PetscErrorCode ierr; 16 PetscInt tmp,i,vl,last; 17 18 PetscFunctionBegin; 19 if (right <= 1) { 20 if (right == 1) { 21 if (v[vdx[0]] > v[vdx[1]]) SWAP(vdx[0],vdx[1],tmp); 22 } 23 PetscFunctionReturn(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 ierr = PetscSortIntWithPermutation_Private(v,vdx,last-1);CHKERRQ(ierr); 33 ierr = PetscSortIntWithPermutation_Private(v,vdx+last+1,right-(last+1));CHKERRQ(ierr); 34 PetscFunctionReturn(0); 35 } 36 37 /*@ 38 PetscSortIntWithPermutation - Computes the permutation of values that gives 39 a sorted sequence. 40 41 Not Collective 42 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. 47 48 Level: intermediate 49 50 Notes: 51 On output i is unchanged and idx[i] is the position of the i-th smallest index in i. 52 53 Concepts: sorting^ints with permutation 54 55 .seealso: PetscSortInt(), PetscSortRealWithPermutation(), PetscSortIntWithArray() 56 @*/ 57 PetscErrorCode PetscSortIntWithPermutation(PetscInt n,const PetscInt i[],PetscInt idx[]) 58 { 59 PetscErrorCode ierr; 60 PetscInt j,k,tmp,ik; 61 62 PetscFunctionBegin; 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 ierr = PetscSortIntWithPermutation_Private(i,idx,n-1);CHKERRQ(ierr); 75 } 76 PetscFunctionReturn(0); 77 } 78 79 /* ---------------------------------------------------------------------- */ 80 81 static PetscErrorCode PetscSortRealWithPermutation_Private(const PetscReal v[],PetscInt vdx[],PetscInt right) 82 { 83 PetscReal vl; 84 PetscErrorCode ierr; 85 PetscInt tmp,i,last; 86 87 PetscFunctionBegin; 88 if (right <= 1) { 89 if (right == 1) { 90 if (v[vdx[0]] > v[vdx[1]]) SWAP(vdx[0],vdx[1],tmp); 91 } 92 PetscFunctionReturn(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 ierr = PetscSortRealWithPermutation_Private(v,vdx,last-1);CHKERRQ(ierr); 102 ierr = PetscSortRealWithPermutation_Private(v,vdx+last+1,right-(last+1));CHKERRQ(ierr); 103 PetscFunctionReturn(0); 104 } 105 106 /*@ 107 PetscSortRealWithPermutation - Computes the permutation of values that gives 108 a sorted sequence. 109 110 Not Collective 111 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. 116 117 Level: intermediate 118 119 Notes: 120 i is unchanged on output. 121 122 Concepts: sorting^doubles with permutation 123 124 .seealso: PetscSortReal(), PetscSortIntWithPermutation() 125 @*/ 126 PetscErrorCode PetscSortRealWithPermutation(PetscInt n,const PetscReal i[],PetscInt idx[]) 127 { 128 PetscErrorCode ierr; 129 PetscInt j,k,tmp; 130 PetscReal ik; 131 132 PetscFunctionBegin; 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 ierr = PetscSortRealWithPermutation_Private(i,idx,n-1);CHKERRQ(ierr); 145 } 146 PetscFunctionReturn(0); 147 } 148 149 static PetscErrorCode PetscSortStrWithPermutation_Private(const char* v[],PetscInt vdx[],PetscInt right) 150 { 151 PetscErrorCode ierr; 152 PetscInt tmp,i,last; 153 PetscBool gt; 154 const char *vl; 155 156 PetscFunctionBegin; 157 if (right <= 1) { 158 if (right == 1) { 159 ierr = PetscStrgrt(v[vdx[0]],v[vdx[1]],>);CHKERRQ(ierr); 160 if (gt) SWAP(vdx[0],vdx[1],tmp); 161 } 162 PetscFunctionReturn(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 ierr = PetscStrgrt(vl,v[vdx[i]],>);CHKERRQ(ierr); 169 if (gt) {last++; SWAP(vdx[last],vdx[i],tmp);} 170 } 171 SWAP(vdx[0],vdx[last],tmp); 172 ierr = PetscSortStrWithPermutation_Private(v,vdx,last-1);CHKERRQ(ierr); 173 ierr = PetscSortStrWithPermutation_Private(v,vdx+last+1,right-(last+1));CHKERRQ(ierr); 174 PetscFunctionReturn(0); 175 } 176 177 /*@C 178 PetscSortStrWithPermutation - Computes the permutation of values that gives 179 a sorted sequence. 180 181 Not Collective 182 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. 187 188 Level: intermediate 189 190 Notes: 191 i is unchanged on output. 192 193 Concepts: sorting^ints with permutation 194 195 .seealso: PetscSortInt(), PetscSortRealWithPermutation() 196 @*/ 197 PetscErrorCode PetscSortStrWithPermutation(PetscInt n,const char* i[],PetscInt idx[]) 198 { 199 PetscErrorCode ierr; 200 PetscInt j,k,tmp; 201 const char *ik; 202 PetscBool gt; 203 204 PetscFunctionBegin; 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 ierr = PetscStrgrt(ik,i[idx[j]],>);CHKERRQ(ierr); 210 if (gt) { 211 SWAP(idx[k],idx[j],tmp); 212 ik = i[idx[k]]; 213 } 214 } 215 } 216 } else { 217 ierr = PetscSortStrWithPermutation_Private(i,idx,n-1);CHKERRQ(ierr); 218 } 219 PetscFunctionReturn(0); 220 } 221