Simple Application Framework  1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines
Functions
Saf::Algo::Sort Namespace Reference

Sorting algorithms. More...

Functions

template<class FwdIter , class Pred >
void BubbleSort (FwdIter begin, FwdIter end, Pred pred)
 Sort the sequence [begin, end) according to pred using the bubble sort algorithm.
template<class FwdIter >
void BubbleSort (FwdIter begin, FwdIter end)
 Sort the sequence [begin, end) from smallest to largest elements using the bubble sort algorithm.
template<class FwdIter , class Pred >
void HeapSort (FwdIter begin, FwdIter end, Pred pred)
 Sort the sequence [begin, end) according to pred using the heap sort algorithm.
template<class FwdIter >
void HeapSort (FwdIter begin, FwdIter end)
 Sort the sequence [begin, end) from smallest to largest elements using the heap sort algorithm.
template<class Iter , class Pred >
void InsertionSort (Iter begin, Iter end, Pred pred)
 Sort the sequence [begin, end) according to pred using the insertion sort algorithm.
template<class Iter >
void InsertionSort (Iter begin, Iter end)
 Sort the sequence [begin, end) from smallest to largest elements using the insertion sort algorithm.
template<class RanIter , class Pred >
void IntroSort (RanIter begin, RanIter end, Pred pred)
 Sort sequence [begin, end) according to pred using the introspective sorting algorithm.
template<class RanIter >
void IntroSort (RanIter begin, RanIter end)
 Sort the sequence [begin, end) from smallest to largest elements using the introspective sorting algorithm.
template<class BidIter , class Pred >
void MergeSort (BidIter begin, BidIter end, Pred pred)
template<class BidIter , class Pred >
void MergeSortInPlace (BidIter begin, BidIter end, Pred pred)
 Sort the sequence [begin, end) according to pred using the in-place mergesort sorting algorithm.
template<class BidIter >
void MergeSortInPlace (BidIter begin, BidIter end)
 Sort the sequence [begin, end) from smallest to largest elements using the in-place mergesort sorting algorithm.
template<class RanIter , class Pred >
void QuickSort (RanIter begin, RanIter end, Pred pred)
 Sort the sequence [begin, end) according to pred using the quicksort sorting algorithm.
template<class RanIter >
void QuickSort (RanIter begin, RanIter end)
 Sort the sequence [begin, end) from smallest to largest elements using the quicksort sorting algorithm.
template<class RanIter , class Pred >
void Sort (RanIter begin, RanIter end, Pred pred)
 Sort sequence [begin, end) according to pred using the default non-stable sorting algorithm.
template<class RanIter >
void Sort (RanIter begin, RanIter end)
 Sort the sequence [begin, end) from smallest to largest elements using the default non-stable sorting algorithm.
template<class RanIter , class Pred >
void SortStable (RanIter begin, RanIter end, Pred pred)
 Sort sequence [begin, end) according to pred using the default stable sorting algorithm.
template<class RanIter >
void SortStable (RanIter begin, RanIter end)
 Sort the sequence [begin, end) from smallest to largest elements using the default stable sorting algorithm.

Detailed Description

Sorting algorithms.

Function Documentation

template<class FwdIter , class Pred >
void Saf::Algo::Sort::BubbleSort ( FwdIter  begin,
FwdIter  end,
Pred  pred 
)

Sort the sequence [begin, end) according to pred using the bubble sort algorithm.

Properties:

  • Minimum iterator category: Forward.
  • Worst-case time complexity: $ \mathcal{O}(n^2) $ where $ n = \mathrm{Range::Distance(begin, end)} $.
  • Space complexity: $ \mathcal{O}(1) $.
  • Stable sort: Yes.
Parameters:
[in]beginIterator to the beginning of the sequence.
[in]endIterator to the end of the sequence.
[in]predBinary comparison predicate.
template<class FwdIter >
void Saf::Algo::Sort::BubbleSort ( FwdIter  begin,
FwdIter  end 
)

Sort the sequence [begin, end) from smallest to largest elements using the bubble sort algorithm.

Properties:

  • Minimum iterator category: Forward.
  • Worst-case time complexity: $ \mathcal{O}(n^2) $ where $ n = \mathrm{Range::Distance(begin, end)} $.
  • Space complexity: $ \mathcal{O}(1) $.
  • Stable sort: Yes.
Parameters:
[in]beginIterator to the beginning of the sequence.
[in]endIterator to the end of the sequence.
template<class FwdIter , class Pred >
void Saf::Algo::Sort::HeapSort ( FwdIter  begin,
FwdIter  end,
Pred  pred 
)

Sort the sequence [begin, end) according to pred using the heap sort algorithm.

Properties:

  • Minimum iterator category: Random-access.
  • Worst-case time complexity: $ \mathcal{O}(n \cdot \log n) $ where $ n = \mathrm{Range::Distance(begin, end)} $.
  • Space complexity: $ \mathcal{O}(1) $.
  • Stable sort: No.
Parameters:
[in]beginIterator to the beginning of the sequence.
[in]endIterator to the end of the sequence.
[in]predBinary comparison predicate.
template<class FwdIter >
void Saf::Algo::Sort::HeapSort ( FwdIter  begin,
FwdIter  end 
)

Sort the sequence [begin, end) from smallest to largest elements using the heap sort algorithm.

Properties:

  • Minimum iterator category: Random-access.
  • Worst-case time complexity: $ \mathcal{O}(n \cdot \log n) $ where $ n = \mathrm{Range::Distance(begin, end)} $.
  • Space complexity: $ \mathcal{O}(1) $.
  • Stable sort: No.
Parameters:
[in]beginIterator to the beginning of the sequence.
[in]endIterator to the end of the sequence.
template<class Iter , class Pred >
void Saf::Algo::Sort::InsertionSort ( Iter  begin,
Iter  end,
Pred  pred 
)

Sort the sequence [begin, end) according to pred using the insertion sort algorithm.

Properties:

  • Minimum iterator category: Forward.
  • Worst-case time complexity: $ \mathcal{O}(n^2) $ where $ n = \mathrm{Range::Distance(begin, end)} $.
  • Space complexity: $ \mathcal{O}(1) $.
  • Stable sort: Yes.
Parameters:
[in]beginIterator to the beginning of the sequence.
[in]endIterator to the end of the sequence.
[in]predBinary comparison predicate.
template<class Iter >
void Saf::Algo::Sort::InsertionSort ( Iter  begin,
Iter  end 
)

Sort the sequence [begin, end) from smallest to largest elements using the insertion sort algorithm.

Properties:

  • Minimum iterator category: Forward.
  • Worst-case time complexity: $ \mathcal{O}(n^2) $ where $ n = \mathrm{Range::Distance(begin, end)} $.
  • Space complexity: $ \mathcal{O}(1) $.
  • Stable sort: Yes.
Parameters:
[in]beginIterator to the beginning of the sequence.
[in]endIterator to the end of the sequence.
template<class RanIter , class Pred >
void Saf::Algo::Sort::IntroSort ( RanIter  begin,
RanIter  end,
Pred  pred 
)

Sort sequence [begin, end) according to pred using the introspective sorting algorithm.

Based on the paper:

  • D. R. Musser: Introspective sorting and selection algorithms. Software: Practice and Experience (Wiley). Vol. 27 (8). 1997.

Properties:

  • Minimum iterator category: Random-access.
  • Worst-case time complexity: $ \mathcal{O}(n \log n) $ where $ n = \mathrm{Range::Distance(begin, end)} $.
  • Worst-case space complexity: $ \mathcal{O}(\log n) $ where $ n = \mathrm{Range::Distance(begin, end)} $.
  • Stable sort: No.
Parameters:
[in]beginIterator to the beginning of the sequence.
[in]endIterator to the end of the sequence.
[in]predBinary comparison predicate.
template<class RanIter >
void Saf::Algo::Sort::IntroSort ( RanIter  begin,
RanIter  end 
)

Sort the sequence [begin, end) from smallest to largest elements using the introspective sorting algorithm.

Based on the paper:

  • D. R. Musser: Introspective sorting and selection algorithms. Software: Practice and Experience (Wiley). Vol. 27 (8). 1997.

Properties:

  • Minimum iterator category: Random-access.
  • Worst-case time complexity: $ \mathcal{O}(n \log n) $ where $ n = \mathrm{Range::Distance(begin, end)} $.
  • Worst-case space complexity: $ \mathcal{O}(\log n) $ where $ n = \mathrm{Range::Distance(begin, end)} $.
  • Stable sort: No.
Parameters:
[in]beginIterator to the beginning of the sequence.
[in]endIterator to the end of the sequence.
template<class BidIter , class Pred >
void Saf::Algo::Sort::MergeSort ( BidIter  begin,
BidIter  end,
Pred  pred 
)
Todo:
Experimental.
template<class BidIter , class Pred >
void Saf::Algo::Sort::MergeSortInPlace ( BidIter  begin,
BidIter  end,
Pred  pred 
)

Sort the sequence [begin, end) according to pred using the in-place mergesort sorting algorithm.

Properties:

  • Minimum iterator category: Bidirectional.
  • Worst-case time complexity: $ \mathcal{O}(n \cdot (\log n)^2) $ where $ n = \mathrm{Range::Distance(begin, end)} $.
  • Worst-case space complexity: $ \mathcal{O}(\log n) $ where $ n = \mathrm{Range::Distance(begin, end)} $.
  • Stable sort: Yes.
Parameters:
[in]beginIterator to the beginning of the sequence.
[in]endIterator to the end of the sequence.
[in]predBinary comparison predicate.
template<class BidIter >
void Saf::Algo::Sort::MergeSortInPlace ( BidIter  begin,
BidIter  end 
)

Sort the sequence [begin, end) from smallest to largest elements using the in-place mergesort sorting algorithm.

Properties:

  • Minimum iterator category: Bidirectional.
  • Worst-case time complexity: $ \mathcal{O}(n \cdot (\log n)^2) $ where $ n = \mathrm{Range::Distance(begin, end)} $.
  • Worst-case space complexity: $ \mathcal{O}(\log n) $ where $ n = \mathrm{Range::Distance(begin, end)} $.
  • Stable sort: Yes.
Parameters:
[in]beginIterator to the beginning of the sequence.
[in]endIterator to the end of the sequence.
template<class RanIter , class Pred >
void Saf::Algo::Sort::QuickSort ( RanIter  begin,
RanIter  end,
Pred  pred 
)

Sort the sequence [begin, end) according to pred using the quicksort sorting algorithm.

Properties:

  • Minimum iterator category: Random-access.
  • Average time complexity: $ \mathcal{O}(n \log n) $ where $ n = \mathrm{Range::Distance(begin, end)} $.
  • Worst-case time complexity: $ \mathcal{O}(n^2) $ where $ n = \mathrm{Range::Distance(begin, end)} $.
  • Worst-case space complexity: $ \mathcal{O}(\log n) $ where $ n = \mathrm{Range::Distance(begin, end)} $.
  • Stable sort: No.
Parameters:
[in]beginIterator to the beginning of the sequence.
[in]endIterator to the end of the sequence.
[in]predBinary comparison predicate.
template<class RanIter >
void Saf::Algo::Sort::QuickSort ( RanIter  begin,
RanIter  end 
)

Sort the sequence [begin, end) from smallest to largest elements using the quicksort sorting algorithm.

Properties:

  • Minimum iterator category: Random-access.
  • Average time complexity: $ \mathcal{O}(n \log n) $ where $ n = \mathrm{Range::Distance(begin, end)} $.
  • Worst-case time complexity: $ \mathcal{O}(n^2) $ where $ n = \mathrm{Range::Distance(begin, end)} $.
  • Worst-case space complexity: $ \mathcal{O}(\log n) $ where $ n = \mathrm{Range::Distance(begin, end)} $.
  • Stable sort: No.
Parameters:
[in]beginIterator to the beginning of the sequence.
[in]endIterator to the end of the sequence.
template<class RanIter , class Pred >
void Saf::Algo::Sort::Sort ( RanIter  begin,
RanIter  end,
Pred  pred 
)

Sort sequence [begin, end) according to pred using the default non-stable sorting algorithm.

Properties:

  • Minimum iterator category: Random-access.
  • Worst-case time complexity: $ \mathcal{O}(n \log n) $ where $ n = \mathrm{|end - begin|} $.
  • Worst-case space complexity: $ \mathcal{O}(\log n) $ where $ n = \mathrm{|end - begin|} $.
  • Stable sort: No.
Parameters:
[in]beginIterator to the beginning of the sequence.
[in]endIterator to the end of the sequence.
[in]predBinary comparison predicate.
template<class RanIter >
void Saf::Algo::Sort::Sort ( RanIter  begin,
RanIter  end 
)

Sort the sequence [begin, end) from smallest to largest elements using the default non-stable sorting algorithm.

Properties:

  • Minimum iterator category: Random-access.
  • Worst-case time complexity: $ \mathcal{O}(n \log n) $ where $ n = \mathrm{|end - begin|} $.
  • Worst-case space complexity: $ \mathcal{O}(\log n) $ where $ n = \mathrm{|end - begin|} $.
  • Stable sort: No.
Parameters:
[in]beginIterator to the beginning of the sequence.
[in]endIterator to the end of the sequence.
template<class RanIter , class Pred >
void Saf::Algo::Sort::SortStable ( RanIter  begin,
RanIter  end,
Pred  pred 
)

Sort sequence [begin, end) according to pred using the default stable sorting algorithm.

Properties:

  • Minimum iterator category: Random-access.
  • Worst-case time complexity: $ \mathcal{O}(n \cdot (\log n)^2) $ where $ n = \mathrm{Range::Distance(begin, end)} $.
  • Worst-case space complexity: $ \mathcal{O}(\log n) $ where $ n = \mathrm{Range::Distance(begin, end)} $.
  • Stable: Yes.
Parameters:
[in]beginIterator to the beginning of the sequence.
[in]endIterator to the end of the sequence.
[in]predBinary comparison predicate.
template<class RanIter >
void Saf::Algo::Sort::SortStable ( RanIter  begin,
RanIter  end 
)

Sort the sequence [begin, end) from smallest to largest elements using the default stable sorting algorithm.

Properties:

  • Minimum iterator category: Random-access.
  • Worst-case time complexity: $ \mathcal{O}(n \cdot (\log n)^2) $ where $ n = \mathrm{Range::Distance(begin, end)} $.
  • Worst-case space complexity: $ \mathcal{O}(\log n) $ where $ n = \mathrm{Range::Distance(begin, end)} $.
  • Stable: Yes.
Parameters:
[in]beginIterator to the beginning of the sequence.
[in]endIterator to the end of the sequence.
Generated on Tue May 8 2012 18:51:21 for Simple Application Framework by   doxygen 1.8.0