Main Page   Namespace List   Class Hierarchy   Compound List   File List   Namespace Members   Compound Members  

quick_sort_algorithm.hh

00001 /*
00002 *  Name:      quick_sort_algorithm.hh
00003 *  Author:    Rafael Jesus Alcantara Perez
00004 *  Summary:   Quick sort algorithm
00005 *  Date:      $Date: 2003/04/14 00:18:35 $
00006 *  Revision:  $Revision: 1.1 $
00007 *
00008 *  Copyright (C) 1994-2002  Rafael Jesus Alcantara Perez <rafa@dedalo-ing.com>
00009 *
00010 *  This program is free software; you can redistribute it and/or modify
00011 *  it under the terms of the GNU General Public License as published by
00012 *  the Free Software Foundation; either version 2 of the License, or
00013 *  (at your option) any later version.
00014 *
00015 *  This program is distributed in the hope that it will be useful,
00016 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
00017 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00018 *  GNU General Public License for more details.
00019 *
00020 *  You should have received a copy of the GNU General Public License
00021 *  along with this program; if not, write to the Free Software
00022 *  Foundation, Inc., 59 Temple Place, Suite 330, Boston,
00023 *  MA 02111-1307, USA.
00024 */
00025 
00026 #ifndef _MPCL_UTIL_STRATEGY_QUICK_SORT_ALGORITHM__
00027 #define _MPCL_UTIL_STRATEGY_QUICK_SORT_ALGORITHM__
00028 
00029 #include "../../exceptions.hh"
00030 #include "sort_algorithm.hh"
00031 
00032 
00034 namespace mpcl
00035 {
00036 
00038   namespace util
00039   {
00040 
00042     namespace strategy
00043     {
00044 
00058       template <typename TSequence>
00059       class TQuickSortAlgorithm : public ISortAlgorithm<TSequence>
00060       {
00061 
00062         public:
00063 
00065           typedef
00066             typename ISortAlgorithm<TSequence>::iterator
00067             iterator;
00068 
00070           typedef
00071             typename ISortAlgorithm<TSequence>::const_iterator
00072             const_iterator;
00073 
00075           typedef
00076             typename ISortAlgorithm<TSequence>::value_type
00077             value_type;
00078 
00079 
00080         public:
00081 
00082           //
00083           //  C O N S T R U C T O R S
00084           //
00085 
00091           void execute (TSequence& rtSOURCE_SEQUENCE)
00092           {
00093             if ( rtSOURCE_SEQUENCE.size() > 1 )
00094             {
00095               sort (rtSOURCE_SEQUENCE.begin(), rtSOURCE_SEQUENCE.end());
00096             }
00097           }
00098 
00099 
00100         protected:
00101 
00102           //
00103           //  S E L E C T O R S
00104           //
00105 
00112           virtual const_iterator median (const TSequence& rktSOURCE_SEQUENCE) const
00113           {
00114             return median (rktSOURCE_SEQUENCE.begin(), rktSOURCE_SEQUENCE.end());
00115           }
00116 
00124           virtual const_iterator median ( const_iterator ktBEGIN_ITER ,
00125                                           const_iterator ktEND_ITER   ) const
00126           {
00127             size_t   zSize = ktEND_ITER - ktBEGIN_ITER;
00128 
00129             if ( ktEND_ITER <= ktBEGIN_ITER )
00130             {
00131               throw TConstraintException ("sequence is empty", __FILE__, __LINE__);
00132             }
00133             return (ktBEGIN_ITER + (zSize / 2));
00134           }
00135 
00142           void sort (iterator tBEGIN_ITER, iterator tEND_ITER)
00143           {
00144 
00145             iterator           tBiggersIter  = tEND_ITER - 1;
00146             iterator           tSmallersIter = tBEGIN_ITER;
00147             const value_type   ktMedian      = *median (tBEGIN_ITER, tEND_ITER);
00148 
00149             //
00150             //  The algorithm needs that tEND_ITER points to the
00151             //  last element, and not to the end of the sequence.
00152             //
00153             --tEND_ITER;
00154             do
00155             {
00156               //
00157               //  Searches the first element bigger than the reference.
00158               //  Searches the last element smaller than the reference.
00159               //
00160               for (; ( *tSmallersIter < ktMedian )      ;++tSmallersIter);
00161               for (; ( ktMedian       < *tBiggersIter ) ;tBiggersIter--);
00162 
00163               //
00164               //  If the sequence isn't partitioned with biggers than reference
00165               //  item, at right, and smallers at left, then swaps the first
00166               //  bigger item (*tBiggersIter) with the last smaller (*tSmallersIter).
00167               //
00168               if ( tSmallersIter <= tBiggersIter )
00169               {
00170                 if ( tSmallersIter < tBiggersIter )
00171                 {
00172                   swap (*tSmallersIter, *tBiggersIter);
00173                 }
00174                 //
00175                 //  Increments the partition iterators.
00176                 //
00177                 --tBiggersIter;
00178                 ++tSmallersIter;
00179               }
00180             } while ( tSmallersIter <= tBiggersIter );
00181 
00182             //
00183             //  Sorts left and right partitions if they aren't sorted yet.
00184             //
00185             if ( tBEGIN_ITER < tBiggersIter )
00186             {
00187               sort (tBEGIN_ITER, tBiggersIter + 1);
00188             }
00189             if ( tSmallersIter < tEND_ITER )
00190             {
00191               sort (tSmallersIter, tEND_ITER + 1);
00192             }
00193 
00194           }  // sort()
00195 
00196       };  // class TQuickSortAlgorithm
00197 
00198     }  // namespace strategy
00199 
00200   }  // namespace util
00201 
00202 }  // namespace mpcl
00203 
00204 
00205 #endif  // not _MPCL_UTIL_STRATEGY_QUICK_SORT_ALGORITHM__

Generated on Mon Oct 13 02:35:23 2003 for MPCL by doxygen1.2.18