home *** CD-ROM | disk | FTP | other *** search
/ Magazyn Amiga Shareware Floppies / ma24.dms / ma24.adf / WOLF3D / sort.c < prev    next >
C/C++ Source or Header  |  1994-01-20  |  2KB  |  58 lines
  1. #include "global.h"
  2. #include "sort.h"
  3.  
  4. /* -------------------------------------------------------------------------
  5.    NAME:    SortZBuffer
  6.    
  7.    AUTHOR:  Unknown (original Commodore 64 basic program)
  8.             C version in 1992 by Terence Russell.
  9.             
  10.    PURPOSE: Sorts an array structure which is defined with an index range of
  11.             0 to (maxElement-1).
  12.             
  13.             The sort is a Metzner Shell sort. I've done several tests on an
  14.             Amiga 500 & 3000 with various sorts of data and have found this
  15.             routine is just as fast as the QuickSort algorithm. As well it
  16.             doesn't have the problem QuickSort has with sorting data which
  17.             is nearly sorted to begin with.
  18.  
  19.    NOTE: No Copyright is claimed on this routine.
  20.    ------------------------------------------------------------------------- */
  21.             
  22. void SORTWORLD(zBufferType *BUFFER, word maxElement)
  23. {
  24.     register word ShellSize = maxElement, loop, index, index2, preCalc;
  25.     register word SWAP;
  26.  
  27.     while(ShellSize = ShellSize >> 1) /* >> 1 is equivalent to / 2 but faster*/
  28.     {
  29.     preCalc = maxElement - ShellSize; /* Faster assembly code! */
  30.     
  31.     for(loop = 0; loop < preCalc; loop++)
  32.     {
  33.         index = loop;
  34.         
  35.         for(;;)
  36.         {
  37.         index2 = index + ShellSize;
  38.                     /* Change > to < for descending values. */
  39.         
  40.         if( BUFFER[index][1] > BUFFER[index2][1])    /* element [x][1] is the comparison element*/
  41.         {
  42.             SWAP = BUFFER[index2][0];
  43.             BUFFER[index2][0] = BUFFER[index][0];    /* move element 0 */
  44.             BUFFER[index][0] = SWAP;
  45.  
  46.             SWAP = BUFFER[index2][1];
  47.             BUFFER[index2][1] = BUFFER[index][1];    /* move element 1 */
  48.             BUFFER[index][1] = SWAP;
  49.  
  50.             index = index - ShellSize;
  51.             if(index < 0) break;
  52.         }
  53.             else break;
  54.         }
  55.     }
  56.     }   
  57. }
  58.