Created
December 21, 2021 02:32
-
-
Save TonyDecvA180XN/071787cd71ea71c8775f62709f7f7066 to your computer and use it in GitHub Desktop.
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 <iostream> | |
| #include <vector> | |
| #include <algorithm> | |
| #include <utility> | |
| #include <random> | |
| #include <chrono> | |
| template<class RandomAccessIterator> | |
| void insertionSort(RandomAccessIterator begin, RandomAccessIterator end) | |
| { | |
| if (begin == end || (begin + 1) == end) return; | |
| for (RandomAccessIterator next = begin + 1; next != end; ++next) | |
| { | |
| RandomAccessIterator drop = next; | |
| while (drop != begin && (*drop < *(drop - 1))) | |
| { | |
| std::swap(*drop, *(drop - 1)); | |
| --drop; | |
| } | |
| } | |
| return; | |
| } | |
| template<class RandomAccessIterator> | |
| RandomAccessIterator quickSortPartition(RandomAccessIterator begin, RandomAccessIterator end) | |
| { | |
| RandomAccessIterator pivot = begin + std::distance(begin, end) - 1; | |
| RandomAccessIterator futurePivot = begin; | |
| for (RandomAccessIterator i = begin; i != end; ++i) | |
| { | |
| if (*i < *pivot) | |
| { | |
| std::swap(*i, *futurePivot); | |
| ++futurePivot; | |
| } | |
| } | |
| std::swap(*pivot, *futurePivot); | |
| return futurePivot; | |
| } | |
| template<class RandomAccessIterator> | |
| void quickSort(RandomAccessIterator begin, RandomAccessIterator end) | |
| { | |
| if (begin >= end) return; | |
| RandomAccessIterator pivot = quickSortPartition(begin, end); | |
| quickSort(begin, pivot); | |
| quickSort(pivot + 1, end); | |
| } | |
| template<class RandomAccessIterator> | |
| void hybridSort(RandomAccessIterator begin, RandomAccessIterator end) | |
| { | |
| if (begin >= end) return; | |
| constexpr size_t recursionThreshold = 128; | |
| if (std::distance(begin, end) >= recursionThreshold) | |
| { | |
| RandomAccessIterator pivot = quickSortPartition(begin, end); | |
| if (std::distance(begin, pivot) < std::distance(pivot, end)) | |
| { | |
| hybridSort(begin, pivot); | |
| hybridSort(pivot + 1, end); | |
| } | |
| else | |
| { | |
| hybridSort(pivot + 1, end); | |
| hybridSort(begin, pivot); | |
| } | |
| } | |
| else | |
| { | |
| insertionSort(begin, end); | |
| } | |
| } | |
| template<class RandomAccessIterator> | |
| std::chrono::microseconds Benchmark( | |
| RandomAccessIterator begin, | |
| RandomAccessIterator end, | |
| void (*sortFunction)(RandomAccessIterator begin, RandomAccessIterator end) | |
| ) | |
| { | |
| auto start = std::chrono::high_resolution_clock::now(); | |
| sortFunction(begin, end); | |
| auto finish = std::chrono::high_resolution_clock::now(); | |
| auto elapsedTime = std::chrono::duration_cast<std::chrono::microseconds>(finish - start); | |
| return elapsedTime; | |
| } | |
| int main() | |
| { | |
| std::mt19937 rng; | |
| std::uniform_int_distribution dist; | |
| static constexpr size_t vectorLength = 100000; | |
| std::vector<int> vInsertion(vectorLength); | |
| std::generate(vInsertion.begin(), vInsertion.end(), [&]() { return static_cast<int>(dist(rng)); }); | |
| decltype(vInsertion) vQuick(vInsertion); | |
| decltype(vInsertion) vStdSort(vInsertion); | |
| decltype(vInsertion) vHybrid(vInsertion); | |
| std::cout << "Sorting " << vectorLength << " elements of type " << typeid(decltype(vInsertion[0])).name() << "." << std::endl; | |
| std::cout << "Insertion sort took " << Benchmark(vInsertion.begin(), vInsertion.end(), insertionSort).count() << " mcs." << std::endl; | |
| std::cout << "Quick sort took " << Benchmark(vQuick.begin(), vQuick.end(), quickSort).count() << " mcs." << std::endl; | |
| std::cout << "std::sort took " << Benchmark(vStdSort.begin(), vStdSort.end(), std::sort).count() << " mcs." << std::endl; | |
| std::cout << "Hybrid sort took " << Benchmark(vHybrid.begin(), vHybrid.end(), hybridSort).count() << " mcs." << std::endl; | |
| if (!std::equal(vInsertion.begin(), vInsertion.end(), vQuick.begin())) std::cout << "Inconsistent results discovered." << std::endl; | |
| if (!std::equal(vInsertion.begin(), vInsertion.end(), vStdSort.begin())) std::cout << "Inconsistent results discovered." << std::endl; | |
| if (!std::equal(vInsertion.begin(), vInsertion.end(), vHybrid.begin())) std::cout << "Inconsistent results discovered." << std::endl; | |
| return 0; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment