home *** CD-ROM | disk | FTP | other *** search
/ io Programmo 21 / IOPROG_21.ISO / SOFT / LIBMAT.ZIP / MATSORT.CPP < prev    next >
Encoding:
C/C++ Source or Header  |  1992-10-16  |  5.3 KB  |  199 lines
  1. /**************************************************/
  2. /*  matsort.c source for MatClass sort functions  */
  3. /**************************************************/
  4.  
  5.  
  6. /**************************************************/
  7. /*            MatClass Source File                */
  8. /*       Copyright of C. R. Birchenhall           */
  9. /*       University of Manchester, UK.            */
  10. /*   MatClass is freeware. This file should be    */
  11. /* made freely available to users of any software */
  12. /* whose creation is wholly or partly dependent   */
  13. /*                on this file.                   */
  14. /**************************************************/
  15.  
  16. #include "matrix.hpp"
  17.  
  18. void matrix::shellSort( void )
  19. {
  20.    // see Sedgwick p.98
  21.    // this is sorted directly
  22.    static char *mName = "shellSort" ;
  23.    matFunc func( mName ) ; debugInfo( func ) ;
  24.    if ( nCols() != 1 )
  25.       errorExit( mName, NOTVC ) ;
  26.    INDEX nr = nRows(), h, i, j ;
  27.    REAL xi ;
  28.    // initialise step length h to be > nr
  29.    for ( h = 1 ; h <= nr ; h = 3 * h + 1 )
  30.       ;
  31.    do {
  32.       h /= 3 ; // reduce step length
  33.       // h-sort
  34.       for ( i = h + 1 ; i <= nr ; i++ ) {
  35.      xi = mat(i) ;
  36.      j = i ;
  37.      while ( j > h ) {
  38.         if ( mat(j-h) < xi )
  39.            break ; // end while
  40.         mat(j) = mat(j-h) ;
  41.         j -= h ;
  42.      } // while
  43.      mat(j) = xi ;
  44.       } // for i
  45.    } while ( h > 1 ) ;
  46. } // shellSort
  47.  
  48. void matrix::shellMap( indexArray& m ) M_CONST
  49. {
  50.    // see Sedgwick p.98
  51.    // this is not sorted but returns a map to the sort
  52.    static char *mName = "shellMap(m)" ;
  53.    matFunc func( mName ) ; debugInfo( func ) ;
  54.    if ( nCols() != 1 )
  55.       errorExit( mName, NOTVC ) ;
  56.    INDEX nr = nRows(), h, i, j, mi ;
  57.    REAL xi ;
  58.    if ( nr != m.length() )
  59.       m.reset(nr) ;
  60.    // initial index map
  61.    for ( i = 1; i <= nr; i++ )
  62.       m(i) = i ;
  63.    // initialise step length h to be > nr
  64.    for ( h = 1 ; h <= nr ; h = 3 * h + 1 )
  65.       ;
  66.    do {
  67.       h /= 3 ; // reduce step length
  68.       // h-sort
  69.       for ( i = h + 1 ; i <= nr ; i++ ) {
  70.      mi = m(i) ;
  71.      xi = mat(mi) ;
  72.      j = i ;
  73.      while ( j > h ) {
  74.         if ( mat(m(j-h)) < xi )
  75.            break ; // end while
  76.         m(j) = m(j-h) ;
  77.         j -= h ;
  78.      } // while
  79.      m(j) = mi ;
  80.       } // for i
  81.    } while ( h > 1 ) ;
  82. } // shellMap
  83.  
  84. void matrix::heapSort( void )
  85. {
  86.    // sort this
  87.    static char *mName = "heapSort" ;
  88.    matFunc func( mName ) ; debugInfo( func ) ;
  89.    if ( nCols() != 1 )
  90.       errorExit( mName, NOTVC ) ;
  91.    INDEX nr = nRows(), bottom, top, parent, child ;
  92.    REAL target;
  93.    bottom = nr ;
  94.    top = ( bottom / 2 ) + 1 ;
  95.    while ( bottom > 1 ) {
  96.       if ( top > 1 ) {  // promote up to form heap
  97.      --top ;
  98.      target = mat( top ) ;
  99.       } else {          // drop largest to bottom
  100.      target = mat( bottom ) ;
  101.      mat( bottom ) = mat(1) ;
  102.      --bottom ;
  103.       } // else
  104.       parent = top ;
  105.       child = 2 * top ;
  106.       while ( child <= bottom ) {
  107.      if ( ( child < bottom ) &&  mat(child) < mat(child+1) )
  108.         ++child ;
  109.      if ( target < mat( child ) ) {
  110.         mat( parent ) = mat( child ) ;
  111.         parent = child ;
  112.         child += parent ;
  113.      } else
  114.         child = bottom + 1 ;
  115.       } // while child
  116.       mat( parent ) = target ;
  117.    } // while bottom
  118. } // heapSort
  119.  
  120. void matrix::heapMap( indexArray& m ) M_CONST
  121. {
  122.    // does not sort this but return index map of sort in m
  123.    static char *mName = "heapMap(m)" ;
  124.    matFunc func( mName ) ; debugInfo( func ) ;
  125.    if ( nCols() != 1 )
  126.       errorExit( mName, NOTVC ) ;
  127.    INDEX nr = nRows(), bottom, top, parent, child, i ;
  128.    INDEX target ;
  129.    REAL  targetValue, childValue ;
  130.    // initial index map
  131.    if ( nr != m.length() )
  132.       m.reset(nr) ;
  133.    for ( i = 1; i <= nr; i++ )
  134.       m(i) = i ;
  135.    bottom = nr ;
  136.    top = ( bottom / 2 ) + 1 ;
  137.    while ( bottom > 1 ) {
  138.       if ( top > 1 ) {  // promote up to form heap
  139.      --top ;
  140.      target = m(top) ;
  141.       } else {          // drop largest to bottom
  142.      target = m(bottom) ;
  143.      m(bottom) = m(1) ;
  144.      --bottom ;
  145.       } // else
  146.       parent = top ;
  147.       child = 2 * top ;
  148.       while ( child <= bottom ) {
  149.      childValue = mat( m(child) ) ;
  150.      if ( ( child < bottom ) &&  childValue < mat( m(child+1) ) )
  151.         ++child ;
  152.      targetValue = mat(target) ;
  153.      if ( targetValue < mat( m(child) ) ) {
  154.         m(parent) = m(child) ;
  155.         parent = child ;
  156.         child += parent ;
  157.      } else
  158.         child = bottom + 1 ;
  159.       } // while child
  160.       m(parent) = target ;
  161.    } // while bottom
  162. } // heapMap
  163.  
  164. indexArray matrix::heapMap( void ) M_CONST
  165. {
  166.    static char *mName = "heapMap()" ;
  167.    matFunc func( mName ) ; debugInfo( func ) ;
  168.    indexArray map( nRows() ) ;
  169.    heapMap( map ) ;
  170.    return map ;
  171. } // matrix::heapMap
  172.  
  173. indexArray matrix::shellMap( void ) M_CONST
  174. {
  175.    static char *mName = "shellMap()" ;
  176.    matFunc func( mName ) ; debugInfo( func ) ;
  177.    indexArray map( nRows() ) ;
  178.    shellMap( map ) ;
  179.    return map ;
  180. } // matrix::shellMap
  181.  
  182. matrix rankings( indexArray& m )
  183. {
  184.    // assumes m is an sort index
  185.    static char *mName = "rankings" ;
  186.    matFunc func( mName ) ; m.debugInfo( func ) ;
  187.    INDEX nr = m.length(), i, k ;
  188.    matrix z( nr ) ;
  189.    for ( i = 1; i <= nr ; i++ ) {
  190.       k = m(i) ;
  191.       if ( ( k < 1 ) || ( k > nr ) ) {
  192.      m.errorij( i, 1 ) ;
  193.      m.errorExit( mName, NRANG ) ;
  194.       } else
  195.      z(k) = (REAL) i ;
  196.    } // for i
  197.    return z ;
  198. } // rankings
  199.