multsort.c

NIST Handwriting OCR Testbed

/*    Inputs a pivot element making comparisons and     */
/*    swaps with other elements in a list until pivot   */
/*    resides at its correct position in the list.      */
/********************************************************/
partition_inc(indexstruct, curindex_i, llen, rlen, ll, lr, rl, rr, p, l, r)
int curindex_i, p, l, r, *llen, *rlen;
INDEX indexstruct;
int *rl, *lr, *ll, *rr;
{
   int i;
   int flag = TRUE;

   *ll = l;
   *rr = r;
   while (flag){
      if (l < p){
         if ((indexstruct->index[curindex_i])[l] >
                         (indexstruct->index[curindex_i])[p]){
            for(i = 0; i < indexstruct->indexnum; i++)
               swap (int, (indexstruct->index[i])[l],
                          (indexstruct->index[i])[p])

            if((indexstruct->itemtype) == INTTYPE)
               swap (int, indexstruct->item[l].i_item,
                          indexstruct->item[p].i_item)
            else
               swap (char *, indexstruct->item[l].p_item,
                             indexstruct->item[p].p_item)
 
            p = l;
	 }
         else
            l++;
      }
      else{
         if (r > p){
            if ((indexstruct->index[curindex_i])[r] <
                            (indexstruct->index[curindex_i])[p]){
               for(i = 0; i < indexstruct->indexnum; i++)
                  swap (int, (indexstruct->index[i])[r],
                             (indexstruct->index[i])[p])
               if((indexstruct->itemtype) == INTTYPE)
                  swap (int, indexstruct->item[r].i_item,
                             indexstruct->item[p].i_item)
               else
                  swap (char *, indexstruct->item[r].p_item,
                                indexstruct->item[p].p_item)
               p = r;
               l++;
	    }
            else
               r--;
	 }
         else{
            flag = FALSE;
            *lr = p - 1;
            *rl = p + 1;
            *llen = *lr - *ll + 1;
            *rlen = *rr - *rl + 1;
	 }
      }
   }
}

/********************************************************/
/* qsort_INDEX_dec:                                     */
/*    This procedure inputs a pointer to an index_      */
/*    struct, the subscript of an index array to be     */
/*    sorted, a left subscript pointing to where the    */
/*    sort is to begin in the index array, and a right  */
/*    subscript where to end. This module invokes a     */
/*    decreasing quick-sort sorting the index array     */
/*    from l to r.                                      */
/********************************************************/
qsort_INDEX_dec(indexstruct, curindex_i, l, r)
INDEX indexstruct;
int curindex_i, l, r;
{
   int left = l;
   int right = r;
   int pivot;
   int llen, rlen;
   int lleft, lright, rleft, rright;

   pushstack(left);
   pushstack(right);
   while(stkptr != stack){
      right = popstack();
      left = popstack();
      if((right - left + 1) > 1){
         pivot = select_pivot(indexstruct->index[curindex_i],left, right);
         partition_dec(indexstruct, curindex_i, &llen, &rlen, &lleft,
                   &lright, &rleft, &rright,pivot, left, right);
         if(llen > rlen){
            pushstack(lleft);
            pushstack(lright);
            pushstack(rleft);
            pushstack(rright);
	 }
         else{
            pushstack(rleft);
            pushstack(rright);
            pushstack(lleft);
            pushstack(lright);
	 }
      }
   }
}

/********************************************************/
/* partition_dec:                                       */
/*    Inputs a pivot element making comparisons and     */
/*    swaps with other elements in a list until pivot   */
/*    resides at its correct position in the list.      */
/********************************************************/
partition_dec(indexstruct, curindex_i, llen, rlen, ll, lr, rl, rr, p, l, r)
int curindex_i, p, l, r, *llen, *rlen;
INDEX indexstruct;
int *rl, *lr, *ll, *rr;
{
   int i;
   int flag = TRUE;

   *ll = l;
   *rr = r;
   while (flag){
      if (l < p){
         if ((indexstruct->index[curindex_i])[l] <
                         (indexstruct->index[curindex_i])[p]){
            for(i = 0; i < indexstruct->indexnum; i++)
               swap (int, (indexstruct->index[i])[l],
                          (indexstruct->index[i])[p])

            if((indexstruct->itemtype) == INTTYPE)
               swap (int, indexstruct->item[l].i_item,
                          indexstruct->item[p].i_item)
            else
               swap (char *, indexstruct->item[l].p_item,
                             indexstruct->item[p].p_item)
 
            p = l;
	 }
         else
            l++;
      }
      else{
         if (r > p){
            if ((indexstruct->index[curindex_i])[r] >
                            (indexstruct->index[curindex_i])[p]){
               for(i = 0; i < indexstruct->indexnum; i++)
                  swap (int, (indexstruct->index[i])[r],
                             (indexstruct->index[i])[p])
               if((indexstruct->itemtype) == INTTYPE)
                  swap (int, indexstruct->item[r].i_item,
                             indexstruct->item[p].i_item)
               else
                  swap (char *, indexstruct->item[r].p_item,
                                indexstruct->item[p].p_item)
               p = r;
               l++;
	    }
            else
               r--;
	 }
         else{
            flag = FALSE;
            *lr = p - 1;
            *rl = p + 1;
            *llen = *lr - *ll + 1;
            *rlen = *rr - *rl + 1;
	 }
      }
   }
}


/********************************************************/
/* select_pivot:                                        */
/*    This module selects a pivot from a list being     */
/*    sorted using the Singleton Method.                */
/********************************************************/
int select_pivot(rnk, l, r)
int l, r;
int rnk[];
{
   int m = (l + r) / 2;

   if (rnk[l] <= rnk[m])
      if (rnk[m] <= rnk[r])
         return(m);
      else
         if (rnk[r] > rnk[l])
            return(r);
         else
            return(l);
   else
      if (rnk[l] < rnk[r])
         return(l);
      else
         if (rnk[r] < rnk[m])
            return(m);
         else
            return(r);
}

/********************************************************/
/* popstack:                                            */
/*    This function decrements the pointer to a         */
/*    globally defined stack array and returns the      */
/*    last element on the stack.                        */
/********************************************************/
int popstack()
{
   if(--stkptr < stack){
      printf("stack underflow error\n");
      exit(1);
   }
   else{
      return(*stkptr);
   }
}

/********************************************************/
/* pushstack:                                           */
/*    This procedure adds an inputted value to a        */
/*    globally defined stack array and increments       */
/*    its pointer to point to the next available        */
/*    position in the stack.                            */
/********************************************************/
pushstack(position)
int position;
{
   *stkptr++ = position;
   if(stkptr > (stack + STACKSIZE)){
      printf("stack overflow error\n");
      exit(1);
   }
}