home *** CD-ROM | disk | FTP | other *** search
/ io Programmo 41 / IOPROG_41.ISO / soft / c++ / NUMCPP11.ZIP / sort.hpp < prev    next >
Encoding:
C/C++ Source or Header  |  1999-05-17  |  5.7 KB  |  218 lines
  1. //===================================================================
  2. // sort.hpp
  3. //
  4. // Version 1.1
  5. //
  6. // Written by:
  7. //   Brent Worden
  8. //   WordenWare
  9. //   email:  Brent@Worden.org
  10. //
  11. // Copyright (c) 1998-1999 WordenWare
  12. //
  13. // Created:  August 28, 1998
  14. // Revised:  April 10, 1999
  15. //===================================================================
  16.  
  17. #ifndef _SORT_HPP_
  18. #define _SORT_HPP_
  19.  
  20. #include "utility.hpp"
  21. #include "descript.hpp"
  22.  
  23. NUM_BEGIN
  24.  
  25. static const int MAX_QSORT = 10;
  26.  
  27. template<class Iter>
  28. inline void isort(Iter first, Iter last)
  29. //-------------------------------------------------------------------
  30. // Sorts the elements of [first, last) into ascending order using
  31. // insertion.
  32. //-------------------------------------------------------------------
  33. {
  34.     isort(first, last, valueType(first));
  35. }
  36.  
  37. template<class Iter, class T>
  38. void isort(Iter first, Iter last, T* type)
  39. //-------------------------------------------------------------------
  40. // Sorts the elements of [first, last) into ascending order using
  41. // insertion.
  42. //-------------------------------------------------------------------
  43. {
  44.     T value;
  45.     Iter iter;
  46.     Iter curr;
  47.  
  48.     for(iter = first + 1; iter != last; ++iter){
  49.         value = *iter;
  50.         curr = iter - 1;
  51.         while(curr >= first && *curr > value){
  52.             *(curr + 1) = *curr;
  53.             curr--;
  54.         }
  55.         *(curr + 1) = value;
  56.     }
  57. };
  58.  
  59. template<class Iter1, class Iter2>
  60. inline void isort2(Iter1 first1, Iter1 last1, Iter2 first2)
  61. //-------------------------------------------------------------------
  62. // Sorts the elements of [first, last) into ascending numerical order
  63. // using insertion while making the corresponding rearrangement of
  64. // the elements of [first2, first2 + (last1 - first1) ).
  65. //-------------------------------------------------------------------
  66. {
  67.     isort2(first1, last1, first2, valueType(first1), valueType(first2));
  68. }
  69.  
  70. template<class Iter1, class Iter2, class T1, class T2>
  71. void isort2(Iter1 first1, Iter1 last1, Iter2 first2, T1* type1, T2* type2)
  72. {
  73.     T1 value1;
  74.     T2 value2;
  75.     Iter1 iter1;
  76.     Iter1 curr1;
  77.     Iter2 iter2;
  78.     Iter2 curr2;
  79.  
  80.     for(iter1 = first1 + 1, iter2 = first2 + 1; iter1 != last1; ++iter1, ++iter2){
  81.         value1 = *iter1;
  82.         value2 = *iter2;
  83.         curr1 = iter1 - 1;
  84.         curr2 = iter2 - 1;
  85.         while(curr1 >= first1 && *curr1 > value1){
  86.             *(curr1 + 1) = *curr1;
  87.             curr1--;
  88.             *(curr2 + 1) = *curr2;
  89.             curr2--;
  90.         }
  91.         *(curr1 + 1) = value1;
  92.         *(curr2 + 1) = value2;
  93.     }
  94. };
  95.  
  96. template<class Iter>
  97. void qsort(Iter first, Iter last)
  98. //-------------------------------------------------------------------
  99. // Sorts the elements of [first, last) into ascending numerical order
  100. // using the Quicksort.
  101. //-------------------------------------------------------------------
  102. {
  103.     Iter loSwap;
  104.     Iter hiSwap;
  105.  
  106.     if(length(first, last) > MAX_QSORT){
  107.         loSwap = first + 1;
  108.         hiSwap = last - 1;
  109.         do {
  110.             while(loSwap <= hiSwap && *loSwap <= *first){
  111.                 ++loSwap;
  112.             }
  113.             while(*hiSwap > *first){
  114.                 --hiSwap;
  115.             }
  116.             if(loSwap < hiSwap){
  117.                 std::iter_swap(loSwap, hiSwap);
  118.             }
  119.         } while(loSwap < hiSwap);
  120.         std::iter_swap(first, hiSwap);
  121.         if(first < hiSwap - 1){
  122.             qsort(first, hiSwap);
  123.         }
  124.         if(hiSwap + 2 < last){
  125.             qsort(hiSwap + 1, last);
  126.         }
  127.     } else {
  128.         isort(first, last);
  129.     }
  130. };
  131.  
  132. template<class Iter1, class Iter2>
  133. void qsort2(Iter1 first1, Iter1 last1, Iter2 first2)
  134. //-------------------------------------------------------------------
  135. // Sorts the elements of [first, last) into ascending numerical order
  136. // using the Quicksort while making the corresponding rearrangement
  137. // of the elements of [first2, first2 + (last1 - first1) ).
  138. //-------------------------------------------------------------------
  139. {
  140.     Iter1 loSwap, hiSwap;
  141.     Iter2 lo2, hi2;
  142.  
  143.     if(length(first1, last1) > MAX_QSORT){
  144.         loSwap = first1 + 1;
  145.         hiSwap = last1 - 1;
  146.         lo2 = first2 + 1;
  147.         hi2 = first2 + (last1 - first1) - 1;
  148.         do {
  149.             while(loSwap <= hiSwap && *loSwap <= *first1){
  150.                 ++loSwap;
  151.                 ++lo2;
  152.             }
  153.             while(*hiSwap > *first1){
  154.                 --hiSwap;
  155.                 --hi2;
  156.             }
  157.             if(loSwap < hiSwap){
  158.                 std::iter_swap(loSwap, hiSwap);
  159.                 std::iter_swap(lo2, hi2);
  160.             }
  161.         } while(loSwap < hiSwap);
  162.     
  163.         std::iter_swap(first1, hiSwap);
  164.         std::iter_swap(first2, hi2);
  165.         if(first1 < hiSwap - 1){
  166.             qsort2(first1, hiSwap, first2);
  167.         }
  168.         if(hiSwap + 2 < last1){
  169.             qsort2(hiSwap + 1, last1, hi2 + 1);
  170.         }
  171.     } else {
  172.         isort2(first1, last1, first2);
  173.     }
  174. };
  175.  
  176. template<class Iter1, class Iter2>
  177. void qsort2key(Iter1 first1, Iter1 last1, Iter2 first2)
  178. //-------------------------------------------------------------------
  179. // Sorts the element of [first1, last1) and [first2, first2 + (last1
  180. // - first1) ) into ascending order using [first1, last1) as the
  181. // primary key and [first2, first2 + (last1 - first1) ) as the
  182. // secondary key.
  183. //-------------------------------------------------------------------
  184. {
  185.     Iter1 key;
  186.     Iter2 lo, hi;
  187.     
  188.     qsort2(first1, last1, first2);
  189.     
  190.     hi = first2;
  191.     while(first1 < last1){
  192.         key = first1;
  193.         lo = hi;
  194.         while(first1 < last1 && *first1 == *key){
  195.             ++first1;
  196.             ++hi;
  197.         }
  198.         if(hi - lo > 0){
  199.             qsort(lo, hi);
  200.         }
  201.     }
  202. };
  203.  
  204. NUM_END
  205.  
  206. #endif
  207.  
  208. //===================================================================
  209. // Revision History
  210. //
  211. // Version 1.0 - 08/28/1998 - New.
  212. // Version 1.1 - 04/10/1999 - Added Numerics namespace.
  213. //                            Added isort1 and isort2.
  214. //                            Applied isort1 and isort2 to small
  215. //                            groups in qsort1 and qsort2.
  216. //===================================================================
  217.  
  218.