Simple Application Framework  1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines
Saf/Algo/Sort/BubbleSort.h
Go to the documentation of this file.
00001 /*
00002     This file is part of Simple Application Framework (Saf) library.
00003     Copyright (C) 2010 - 2012 Ondrej Danek <ondrej.danek@gmail.com>
00004 
00005     This library is free software: you can redistribute it and/or modify
00006     it under the terms of the GNU General Public License as published 
00007     by the Free Software Foundation, either version 3 of the License, or
00008     (at your option) any later version.
00009 
00010     Saf is distributed in the hope that it will be useful,
00011     but WITHOUT ANY WARRANTY; without even the implied warranty of
00012     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00013     GNU General Public License for more details.
00014 
00015     You should have received a copy of the GNU General Public License
00016     along with Simple Application Framework library. If not, 
00017     see <http://www.gnu.org/licenses/>.
00018 */
00019 
00028 #ifndef SAF_ALGO_SORT_BUBBLESORT_H
00029 #define SAF_ALGO_SORT_BUBBLESORT_H
00030 
00031 #include "../../Type.h"
00032 #include "../Swap.h"
00033 #include "../Predicate.h"
00034 
00035 namespace Saf
00036 {
00037     namespace Algo
00038     {        
00040         namespace Sort
00041         {
00056             template <class FwdIter, class Pred>
00057             void BubbleSort(FwdIter begin, FwdIter end, Pred pred)
00058             {
00059                 FwdIter sentinel = end;
00060 
00061                 while (begin != sentinel)
00062                 {
00063                     FwdIter curItem = begin;
00064                     FwdIter nextItem = begin;
00065                     FwdIter newSentinel = begin;
00066 
00067                     while (++nextItem != sentinel)
00068                     {
00069                         if (pred(*nextItem, *curItem))
00070                         {
00071                             Saf::Algo::Swap(*nextItem, *curItem);
00072                             newSentinel = nextItem;
00073                         }
00074 
00075                         ++curItem;
00076                     }
00077 
00078                     sentinel = newSentinel;
00079                 }
00080             }
00081 
00095             template <class FwdIter>
00096             void BubbleSort(FwdIter begin, FwdIter end)
00097             {
00098                 Predicate::Less<typename Type::IteratorTraits<FwdIter>::ValType> pred;
00099                 BubbleSort(begin, end, pred);
00100             }
00101         }
00102     }
00103 }
00104 
00105 #endif