1: /*$Id: sorti.c,v 1.30 2001/08/06 21:14:16 bsmith Exp $*/
  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: /* -----------------------------------------------------------------------*/

 17: #undef __FUNCT__  
 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 int PetscSortInt_Private(int *v,int right)
 25: {
 26:   int i,vl,last,tmp,ierr;

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

 47: #undef __FUNCT__  
 49: /*@
 50:    PetscSortInt - Sorts an array of integers in place in increasing order.

 52:    Not Collective

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

 58:    Level: intermediate

 60:    Concepts: sorting^ints

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

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

 85: #define SWAP2(a,b,c,d,t) {t=a;a=b;b=t;t=c;c=d;d=t;}

 87: /* -----------------------------------------------------------------------*/

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

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

119: #undef __FUNCT__  
121: /*@
122:    PetscSortIntWithArray - Sorts an array of integers in place in increasing order;
123:        changes a second array to match the sorted first array.

125:    Not Collective

127:    Input Parameters:
128: +  n  - number of values
129: .  i  - array of integers
130: -  I - second array if integers

132:    Level: intermediate

134:    Concepts: sorting^ints with array

136: .seealso: PetscSortReal(), PetscSortIntPermutation(), PetscSortInt()
137: @*/
138: int PetscSortIntWithArray(int n,int i[],int I[])
139: {
140:   int ierr,j,k,tmp,ik;

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