Last active
May 29, 2024 00:04
-
-
Save svdamani/dc57e4d1b00342d4507d to your computer and use it in GitHub Desktop.
Sorting Algorithms using Iterators in C++
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <algorithm> | |
template <class Iterator> | |
inline void BubbleSort(Iterator begin, Iterator end) { | |
for (Iterator i = begin; i != end; ++i) | |
for (Iterator j = begin; j < i; ++j) | |
if (*i < *j) | |
std::iter_swap(i, j); | |
} | |
template <class Iterator> | |
void InsertionSort(Iterator begin, Iterator end) { | |
std::iter_swap(begin, std::min_element(begin, end)); | |
for (Iterator b = begin; ++b < end; begin = b) | |
for (Iterator c = b; *c < *begin; --c, --begin) | |
std::iter_swap(begin, c); | |
} | |
template <class Iterator> | |
inline void SelectionSort(Iterator begin, Iterator end) { | |
for (Iterator i = begin; i != end; ++i) | |
std::iter_swap(i, std::min_element(i, end)); | |
} | |
template <class Iterator> | |
inline void QuickSort(Iterator begin, Iterator end) { | |
if (end <= begin) return; | |
Iterator pivot = begin, middle = begin + 1; | |
for (Iterator i = begin + 1; i < end; ++i) { | |
if (*i < *pivot) { | |
std::iter_swap(i, middle); | |
++middle; | |
} | |
} | |
std::iter_swap(begin, middle - 1); | |
QuickSort(begin, middle - 1); | |
QuickSort(middle, end); | |
} | |
template <class Iterator> | |
inline void MergeSort(Iterator begin, Iterator end) { | |
if (end <= begin + 1) return; | |
Iterator middle = begin + (end - begin) / 2; | |
MergeSort(begin, middle); | |
MergeSort(middle, end); | |
std::inplace_merge(begin, middle, end); | |
} | |
template <class Iterator> | |
inline void HeapSort(Iterator begin, Iterator end) { | |
while (begin != end) | |
std::pop_heap(begin, end--); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
looks ok but how supporting the third parameter compare