home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / sys / amiga / programmer / 6333 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  2.4 KB
  1. Path: EU.net!sun4nl!xs4all!usenet
  2. From: muaddib@xs4all.nl (Thomas van Gulick)
  3. Newsgroups: comp.lang.c,comp.sys.amiga.programmer
  4. Subject: MY SORT DOESN'T QUICK!
  5. Date: 26 Mar 1996 20:55:14 GMT
  6. Organization: XS4ALL, networking for the masses
  7. Message-ID: <2082.6659T1310T2974@xs4all.nl>
  8. NNTP-Posting-Host: undiscovered.xs4all.nl
  9. X-Newsreader: THOR 2.22 (Amiga;TCP/IP) *UNREGISTERED*
  10.  
  11. Help! My Sort doesn't Quick (ie, it doesn't work for all inputs!)
  12. Something goes wrong when the array is being split into two parts,
  13. but how to solve it, beats me. (ULONG = unsigned long btw)
  14.  
  15. The array where this function fails:
  16.  
  17. { 110, 1664, 96781, 1, 5, 10, 1120, 10, 130, 10 }
  18.  
  19. VOID
  20. QuickSort
  21. (
  22.     ULONG   Array[],
  23.     ULONG   lo0,
  24.     ULONG   hi0
  25. )
  26. {
  27.     ULONG lo = lo0;
  28.     ULONG hi = hi0;
  29.  
  30.     if( lo < hi )
  31.     {
  32.         ULONG mid;
  33.  
  34.         mid = Array[ ( lo + hi ) / 2 ];
  35.  
  36.         while( lo < hi )
  37.         {
  38.             while( Array[ lo ] < mid )
  39.                 lo ++;
  40.  
  41.             while( Array[ hi ] > mid )
  42.                 hi --;
  43.  
  44.             if( lo < hi )
  45.             {
  46.                 ULONG swap;
  47.  
  48.                 swap        = Array[ lo ];
  49.                 Array[ lo ] = Array[ hi ];
  50.                 Array[ hi ] = swap;
  51.  
  52.                 lo ++;
  53.                 hi --;
  54.             }
  55.         }
  56.         QuickSort( Array, lo0, hi );
  57.         QuickSort( Array, lo == hi ? lo + 1 : lo, hi0 );
  58.     }
  59. }
  60.  
  61. An other version I tried was: (but this one uses some more instructions
  62. and is therefore a bit slower)
  63.  
  64. VOID
  65. QuickSort
  66. (
  67.     ULONG   Array[],
  68.     ULONG   lo0,
  69.     ULONG   hi0
  70. )
  71. {
  72.     ULONG lo = lo0;
  73.     ULONG hi = hi0;
  74.  
  75.     if( lo < hi )
  76.     {
  77.         ULONG mid;
  78.  
  79.         mid = Array[ ( lo + hi ) / 2 ];
  80.  
  81.         while( lo < hi )
  82.         {
  83.             ULONG swap;
  84.  
  85.             while( lo < hi && Array[ lo ] < mid )
  86.                 lo ++;
  87.  
  88.             while( lo < hi && Array[ hi ] >= mid )
  89.                 hi --;
  90.  
  91.             swap        = Array[ lo ];
  92.             Array[ lo ] = Array[ hi ];
  93.             Array[ hi ] = swap;
  94.  
  95.  
  96.         }
  97.         if( hi < lo )
  98.         {
  99.             ULONG swap;
  100.  
  101.             swap = hi;
  102.             hi   = lo;
  103.             lo   = swap;
  104.         }
  105.  
  106.         QuickSort( Array, lo0, lo );
  107.         QuickSort( Array, lo == lo0 ? lo + 1 : lo, hi0 );
  108.     }
  109. }
  110.  
  111. I need an answer or solution as soon as possible! It's of a live saving matter!
  112. (Well sort of:)
  113.  
  114. Oh, and don't tell me it is built into my compiler.
  115.  
  116. Thomas
  117. --
  118. http://www.xs4all.nl/~muaddib/mf/
  119.  
  120.