1: /*$Id: sortip.c,v 1.37 2001/08/07 21:29:06 bsmith Exp $*/
  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 petsc.h
 10:  #include petscsys.h

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

 14: #undef __FUNCT__  
 16: static int PetscSortIntWithPermutation_Private(const int v[],int vdx[],int right)
 17: {
 18:   int ierr,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: }

 39: #undef __FUNCT__  
 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:    i is unchanged on output.

 57:    Concepts: sorting^ints with permutation

 59: .seealso: PetscSortInt(), PetscSortRealWithPermutation()
 60:  @*/
 61: int PetscSortIntWithPermutation(int n,const int i[],int idx[])
 62: {
 63:   int ierr,j,k,tmp,ik;

 66:   if (n<8) {
 67:     for (k=0; k<n; k++) {
 68:       ik = i[idx[k]];
 69:       for (j=k+1; j<n; j++) {
 70:         if (ik > i[idx[j]]) {
 71:           SWAP(idx[k],idx[j],tmp);
 72:           ik = i[idx[k]];
 73:         }
 74:       }
 75:     }
 76:   } else {
 77:     PetscSortIntWithPermutation_Private(i,idx,n-1);
 78:   }
 79:   return(0);
 80: }

 82: /* ---------------------------------------------------------------------- */

 84: #undef __FUNCT__  
 86: static int PetscSortRealWithPermutation_Private(const PetscReal v[],int vdx[],int right)
 87: {
 88:   PetscReal vl;
 89:   int       ierr,tmp,i,last;

 92:   if (right <= 1) {
 93:     if (right == 1) {
 94:       if (v[vdx[0]] > v[vdx[1]]) SWAP(vdx[0],vdx[1],tmp);
 95:     }
 96:     return(0);
 97:   }
 98:   SWAP(vdx[0],vdx[right/2],tmp);
 99:   vl   = v[vdx[0]];
100:   last = 0;
101:   for (i=1; i<=right; i++) {
102:     if (v[vdx[i]] < vl) {last++; SWAP(vdx[last],vdx[i],tmp);}
103:   }
104:   SWAP(vdx[0],vdx[last],tmp);
105:   PetscSortRealWithPermutation_Private(v,vdx,last-1);
106:   PetscSortRealWithPermutation_Private(v,vdx+last+1,right-(last+1));
107:   return(0);
108: }

110: #undef __FUNCT__  
112: /*@
113:    PetscSortRealWithPermutation - Computes the permutation of values that gives 
114:    a sorted sequence.

116:    Not Collective

118:    Input Parameters:
119: +  n  - number of values to sort
120: .  i  - values to sort
121: -  idx - permutation array.  Must be initialized to 0:n-1 on input.

123:    Level: intermediate

125:    Notes: 
126:    i is unchanged on output.

128:    Concepts: sorting^doubles with permutation

130: .seealso: PetscSortReal(), PetscSortIntWithPermutation()
131:  @*/
132: int PetscSortRealWithPermutation(int n,const PetscReal i[],int idx[])
133: {
134:   int       j,k,tmp,ierr;
135:   PetscReal ik;

138:   if (n<8) {
139:     for (k=0; k<n; k++) {
140:       ik = i[idx[k]];
141:       for (j=k+1; j<n; j++) {
142:         if (ik > i[idx[j]]) {
143:           SWAP(idx[k],idx[j],tmp);
144:           ik = i[idx[k]];
145:         }
146:       }
147:     }
148:   } else {
149:     PetscSortRealWithPermutation_Private(i,idx,n-1);
150:   }
151:   return(0);
152: }