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 PETSC_DLLEXPORT 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 PETSC_DLLEXPORT PetscSortIntWithArray(PetscInt n,PetscInt i[],PetscInt I[])
    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],I[k],I[j],tmp);
    152:           ik = i[k];
    153:         }
    154:       }
    155:     }
    156:   } else {
    157:     PetscSortIntWithArray_Private(i,I,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 PETSC_DLLEXPORT PetscSortIntWithScalarArray(PetscInt n,PetscInt i[],PetscScalar I[])
    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],I[k],I[j],tmp,stmp);
    227:           ik = i[k];
    228:         }
    229:       }
    230:     }
    231:   } else {
    232:     PetscSortIntWithScalarArray_Private(i,I,n-1);
    233:   }
    234:   return(0);
    235: }