Simple Application Framework
1
|
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