SourceForge.jp

list_sort.h

説明を見る。
00001 #ifndef __STX_LIST_SORT_H_
00002 #define __STX_LIST_SORT_H_
00003 
00004 
00005 namespace stx{
00006 
00007 
00008 template <class BidirectionalIterator>
00009 void comb_sort(BidirectionalIterator first,
00010           BidirectionalIterator last) 
00011 {
00012   int gap = static_cast<int>(std::distance(first, last));
00013   if ( gap < 1 ) {
00014       return;
00015   }
00016   BidirectionalIterator first2 = last;
00017   bool swapped = false;
00018   do {
00019     int newgap = (gap*10+3)/13;
00020     if ( newgap < 1 ) newgap = 1;
00021     std::advance(first2, newgap-gap);
00022     gap = newgap;
00023     swapped = false;
00024     for ( BidirectionalIterator target1 = first, target2 = first2;
00025           target2 != last;
00026           ++target1, ++target2) {
00027       if ( *target2 < *target1 ) {
00028         std::iter_swap(target1, target2);
00029         swapped = true;
00030       }
00031     }
00032   } while ( (gap > 1) || swapped );
00033 }
00034 
00035 template <class BidirectionalIterator, class Predicate>
00036 void comb_sort(BidirectionalIterator first,
00037           BidirectionalIterator last,
00038           Predicate pr) 
00039 {
00040   int gap = static_cast<int>(std::distance(first, last));
00041   if ( gap < 1 ) {
00042       return;
00043   }
00044   BidirectionalIterator first2 = last;
00045   bool swapped = false;
00046   do {
00047     int newgap = (gap*10+3)/13;
00048     if ( newgap < 1 ) newgap = 1;
00049     std::advance(first2, newgap - gap);
00050     gap = newgap;
00051     swapped = false;
00052     for ( BidirectionalIterator target1 = first, target2 = first2;
00053           target2 != last;
00054           ++target1, ++target2) {
00055       if ( pr(*target2, *target1) ) {
00056         std::iter_swap(target1, target2);
00057         swapped = true;
00058       }
00059     }
00060   } while ( (gap > 1) || swapped );
00061 }
00062 
00063 
00064 }//end of stx namespace
00065 
00066 #endif

dkutil 1.02リリース前 d金魚専用マニュアルバージョンに対してSun Dec 28 21:23:08 2003に生成されました。 doxygen 1.3.5