Something went wrong. Try again.
Java--'s containers projects.intra.42.fr/projects/cpp-module-09
Something went wrong. Try again.
4.2 kB · 129 lines
C++
at main
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130#include <PmergeMe.hpp>
#include <algorithm>#include <cstdlib>#include <ctime>#include <iostream>#include <sys/time.h>#include <utility>
PmergeMe::PmergeMe() {}
PmergeMe::PmergeMe(const PmergeMe& other) { (void)other; // yeag...}
static std::vector<size_t> generateJacobsthal(const size_t n) { std::vector<size_t> jacobsthal;
jacobsthal.push_back(0); jacobsthal.push_back(1); while (jacobsthal.back() < n) { const size_t next = jacobsthal[jacobsthal.size() - 1] + 2 * jacobsthal[jacobsthal.size() - 2]; jacobsthal.push_back(next); }
return jacobsthal;}
template <typename Container> Container fordJohnsonSortRange(const Container& input) { typedef typename Container::value_type ValueType; typedef std::pair<ValueType, ValueType> PairType;
const size_t size = input.size(); if (size <= 1) return input;
std::vector<PairType> pairs; for (size_t i = 0; i + 1 < size; i += 2) { if (input[i] <= input[i + 1]) { pairs.push_back(std::make_pair(input[i], input[i + 1])); } else { pairs.push_back(std::make_pair(input[i + 1], input[i])); } }
Container largerElements; for (size_t i = 0; i < pairs.size(); ++i) largerElements.push_back(pairs[i].second);
largerElements = fordJohnsonSortRange(largerElements);
if (pairs.empty()) return largerElements;
const typename Container::iterator firstUpper = std::upper_bound(largerElements.begin(), largerElements.end(), pairs[0].second); const typename Container::iterator firstPosition = std::upper_bound(largerElements.begin(), firstUpper, pairs[0].first); largerElements.insert(firstPosition, pairs[0].first);
const std::vector<size_t> jacobsthal = generateJacobsthal(pairs.size()); for (size_t i = 3; i < jacobsthal.size() && jacobsthal[i - 1] < pairs.size(); ++i) { const size_t start = jacobsthal[i - 1]; const size_t end = std::min(jacobsthal[i] - 1, pairs.size() - 1);
for (size_t idx = end; idx >= start; --idx) { const typename Container::iterator upper = std::upper_bound(largerElements.begin(), largerElements.end(), pairs[idx].second); const typename Container::iterator position = std::upper_bound(largerElements.begin(), upper, pairs[idx].first); largerElements.insert(position, pairs[idx].first); } }
if (size % 2 == 1) { const typename Container::iterator position = std::upper_bound(largerElements.begin(), largerElements.end(), input[size - 1]); largerElements.insert(position, input[size - 1]); }
return largerElements;}template <typename Container> void fordJohnsonSort(Container& container) { container = fordJohnsonSortRange(container); }
template std::vector<int> fordJohnsonSortRange<std::vector<int> >(const std::vector<int>&);template std::deque<int> fordJohnsonSortRange<std::deque<int> >(const std::deque<int>&);
template void fordJohnsonSort<std::vector<int> >(std::vector<int>&);template void fordJohnsonSort<std::deque<int> >(std::deque<int>&);
static double elapsedMicroseconds(const timespec& start, const timespec& end) { return (static_cast<double>(end.tv_sec - start.tv_sec) * 1000000 + static_cast<double>(end.tv_nsec - start.tv_nsec)) / 1000; }
static std::ostream& operator<<(std::ostream& stream, const std::vector<int>& vector) { for (size_t i = 0; i < vector.size(); ++i) { stream << vector[i]; if (i + 1 < vector.size()) stream << " "; }
return stream; }
void PmergeMe::sort(std::vector<int>& vector, std::deque<int>& deque) { { std::cout << "Before: " << vector << std::endl; timespec start, end;
clock_gettime(CLOCK_MONOTONIC, &start); fordJohnsonSort(vector); clock_gettime(CLOCK_MONOTONIC, &end);
std::cout << "After: " << vector << std::endl; std::cout << "Time to process a range of " << vector.size() << " elements with std::vector : " << elapsedMicroseconds(start, end) << " us" << std::endl; }
{ timespec start, end;
clock_gettime(CLOCK_MONOTONIC, &start); fordJohnsonSort(deque); clock_gettime(CLOCK_MONOTONIC, &end);
std::cout << "Time to process a range of " << deque.size() << " elements with std::deque : " << elapsedMicroseconds(start, end) << " us" << std::endl; }}
PmergeMe& PmergeMe::operator=(const PmergeMe& other) { if (this == &other) return *this;
return *this;}
PmergeMe::~PmergeMe() {}