1 #define PETSC_DLL 2 /* 3 This file contains routines for sorting doubles. Values are sorted in place. 4 These are provided because the general sort routines incur a great deal 5 of overhead in calling the comparision routines. 6 7 */ 8 #include "petsc.h" /*I "petsc.h" I*/ 9 #include "petscsys.h" /*I "petscsys.h" I*/ 10 11 #define SWAP(a,b,t) {t=a;a=b;b=t;} 12 13 #undef __FUNCT__ 14 #define __FUNCT__ "PetscSortReal_Private" 15 /* A simple version of quicksort; taken from Kernighan and Ritchie, page 87 */ 16 static PetscErrorCode PetscSortReal_Private(PetscReal *v,PetscInt right) 17 { 18 PetscInt i,last; 19 PetscReal vl,tmp; 20 21 PetscFunctionBegin; 22 if (right <= 1) { 23 if (right == 1) { 24 if (v[0] > v[1]) SWAP(v[0],v[1],tmp); 25 } 26 PetscFunctionReturn(0); 27 } 28 SWAP(v[0],v[right/2],tmp); 29 vl = v[0]; 30 last = 0; 31 for (i=1; i<=right; i++) { 32 if (v[i] < vl) {last++; SWAP(v[last],v[i],tmp);} 33 } 34 SWAP(v[0],v[last],tmp); 35 PetscSortReal_Private(v,last-1); 36 PetscSortReal_Private(v+last+1,right-(last+1)); 37 PetscFunctionReturn(0); 38 } 39 40 #undef __FUNCT__ 41 #define __FUNCT__ "PetscSortReal" 42 /*@ 43 PetscSortReal - Sorts an array of doubles in place in increasing order. 44 45 Not Collective 46 47 Input Parameters: 48 + n - number of values 49 - v - array of doubles 50 51 Level: intermediate 52 53 Concepts: sorting^doubles 54 55 .seealso: PetscSortInt(), PetscSortRealWithPermutation() 56 @*/ 57 PetscErrorCode PETSC_DLLEXPORT PetscSortReal(PetscInt n,PetscReal v[]) 58 { 59 PetscInt j,k; 60 PetscReal tmp,vk; 61 62 PetscFunctionBegin; 63 if (n<8) { 64 for (k=0; k<n; k++) { 65 vk = v[k]; 66 for (j=k+1; j<n; j++) { 67 if (vk > v[j]) { 68 SWAP(v[k],v[j],tmp); 69 vk = v[k]; 70 } 71 } 72 } 73 } else { 74 PetscSortReal_Private(v,n-1); 75 } 76 PetscFunctionReturn(0); 77 } 78 79 80 81 #undef __FUNCT__ 82 #define __FUNCT__ "PetscSortSplit" 83 /*@ 84 PetscSortSplit - Quick-sort split of an array in place. 85 86 Not Collective 87 88 Input Parameters: 89 + ncut - splitig index 90 . n - number of values to sort 91 . a - array of values 92 - idx - index for array a 93 94 Output Parameters: 95 + a - permuted array of values such that its elements satisfy: 96 abs(a[i]) >= abs(a[ncut-1]) for i < ncut and 97 abs(a[i]) <= abs(a[ncut-1]) for i >= ncut 98 - idx - permuted index of array a 99 100 Level: intermediate 101 102 Concepts: sorting^doubles 103 104 .seealso: PetscSortInt(), PetscSortRealWithPermutation() 105 @*/ 106 PetscErrorCode PETSC_DLLEXPORT PetscSortSplit(PetscInt ncut,PetscInt n,PetscScalar a[],PetscInt idx[]) 107 { 108 PetscInt i,mid,last,itmp,j,first; 109 PetscScalar d,tmp; 110 PetscReal abskey; 111 112 PetscFunctionBegin; 113 first = 0; 114 last = n-1; 115 if (ncut < first || ncut > last) PetscFunctionReturn(0); 116 117 while (1){ 118 mid = first; 119 abskey = (d = a[mid],PetscAbsScalar(d)); 120 i = last; 121 for (j = first + 1; j <= i; ++j) { 122 if ((d = a[j],PetscAbsScalar(d)) >= abskey) { 123 ++mid; 124 /* interchange */ 125 tmp = a[mid]; itmp = idx[mid]; 126 a[mid] = a[j]; idx[mid] = idx[j]; 127 a[j] = tmp; idx[j] = itmp; 128 } 129 } 130 131 /* interchange */ 132 tmp = a[mid]; itmp = idx[mid]; 133 a[mid] = a[first]; idx[mid] = idx[first]; 134 a[first] = tmp; idx[first] = itmp; 135 136 /* test for while loop */ 137 if (mid == ncut) { 138 break; 139 } else if (mid > ncut){ 140 last = mid - 1; 141 } else { 142 first = mid + 1; 143 } 144 } 145 PetscFunctionReturn(0); 146 } 147