---

quick_sort_algorithm.hh

/*
*  Name:      quick_sort_algorithm.hh
*  Author:    Rafael Jesus Alcantara Perez
*  Summary:   Quick sort algorithm
*  Date:      $Date: 2003/04/14 00:18:35 $
*  Revision:  $Revision: 1.1 $
*
*  Copyright (C) 1994-2002  Rafael Jesus Alcantara Perez <rafa@dedalo-ing.com>
*
*  This program is free software; you can redistribute it and/or modify
*  it under the terms of the GNU General Public License as published by
*  the Free Software Foundation; either version 2 of the License, or
*  (at your option) any later version.
*
*  This program is distributed in the hope that it will be useful,
*  but WITHOUT ANY WARRANTY; without even the implied warranty of
*  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
*  GNU General Public License for more details.
*
*  You should have received a copy of the GNU General Public License
*  along with this program; if not, write to the Free Software
*  Foundation, Inc., 59 Temple Place, Suite 330, Boston,
*  MA 02111-1307, USA.
*/

#ifndef _MPCL_UTIL_STRATEGY_QUICK_SORT_ALGORITHM__
#define _MPCL_UTIL_STRATEGY_QUICK_SORT_ALGORITHM__

#include "../../exceptions.hh"
#include "sort_algorithm.hh"


namespace mpcl
{

  namespace util
  {

    namespace strategy
    {

      template <typename TSequence>
      class TQuickSortAlgorithm : public ISortAlgorithm<TSequence>
      {

        public:

          typedef
            typename ISortAlgorithm<TSequence>::iterator
            iterator;

          typedef
            typename ISortAlgorithm<TSequence>::const_iterator
            const_iterator;

          typedef
            typename ISortAlgorithm<TSequence>::value_type
            value_type;


        public:

          //
          //  C O N S T R U C T O R S
          //

          void execute (TSequence& rtSOURCE_SEQUENCE)
          {
            if ( rtSOURCE_SEQUENCE.size() > 1 )
            {
              sort (rtSOURCE_SEQUENCE.begin(), rtSOURCE_SEQUENCE.end());
            }
          }


        protected:

          //
          //  S E L E C T O R S
          //

          virtual const_iterator median (const TSequence& rktSOURCE_SEQUENCE) const
          {
            return median (rktSOURCE_SEQUENCE.begin(), rktSOURCE_SEQUENCE.end());
          }

          virtual const_iterator median ( const_iterator ktBEGIN_ITER ,
                                          const_iterator ktEND_ITER   ) const
          {
            size_t   zSize = ktEND_ITER - ktBEGIN_ITER;

            if ( ktEND_ITER <= ktBEGIN_ITER )
            {
              throw TConstraintException ("sequence is empty", __FILE__, __LINE__);
            }
            return (ktBEGIN_ITER + (zSize / 2));
          }

          void sort (iterator tBEGIN_ITER, iterator tEND_ITER)
          {

            iterator           tBiggersIter  = tEND_ITER - 1;
            iterator           tSmallersIter = tBEGIN_ITER;
            const value_type   ktMedian      = *median (tBEGIN_ITER, tEND_ITER);

            //
            //  The algorithm needs that tEND_ITER points to the
            //  last element, and not to the end of the sequence.
            //
            --tEND_ITER;
            do
            {
              //
              //  Searches the first element bigger than the reference.
              //  Searches the last element smaller than the reference.
              //
              for (; ( *tSmallersIter < ktMedian )      ;++tSmallersIter);
              for (; ( ktMedian       < *tBiggersIter ) ;tBiggersIter--);

              //
              //  If the sequence isn't partitioned with biggers than reference
              //  item, at right, and smallers at left, then swaps the first
              //  bigger item (*tBiggersIter) with the last smaller (*tSmallersIter).
              //
              if ( tSmallersIter <= tBiggersIter )
              {
                if ( tSmallersIter < tBiggersIter )
                {
                  swap (*tSmallersIter, *tBiggersIter);
                }
                //
                //  Increments the partition iterators.
                //
                --tBiggersIter;
                ++tSmallersIter;
              }
            } while ( tSmallersIter <= tBiggersIter );

            //
            //  Sorts left and right partitions if they aren't sorted yet.
            //
            if ( tBEGIN_ITER < tBiggersIter )
            {
              sort (tBEGIN_ITER, tBiggersIter + 1);
            }
            if ( tSmallersIter < tEND_ITER )
            {
              sort (tSmallersIter, tEND_ITER + 1);
            }

          }  // sort()

      };  // class TQuickSortAlgorithm

    }  // namespace strategy

  }  // namespace util

}  // namespace mpcl


#endif  // not _MPCL_UTIL_STRATEGY_QUICK_SORT_ALGORITHM__

---