141 lines
3.9 KiB
C++
141 lines
3.9 KiB
C++
/* ************************************************************************** */
|
|
/* */
|
|
/* ::: :::::::: */
|
|
/* PmergeMe.cpp :+: :+: :+: */
|
|
/* +:+ +:+ +:+ */
|
|
/* By: adjoly <adjoly@student.42angouleme.fr> +#+ +:+ +#+ */
|
|
/* +#+#+#+#+#+ +#+ */
|
|
/* Created: 2025/06/04 13:28:23 by adjoly #+# #+# */
|
|
/* Updated: 2025/06/04 14:05:14 by adjoly ### ########.fr */
|
|
/* */
|
|
/* ************************************************************************** */
|
|
|
|
#include <PmergeMe.hpp>
|
|
#include <algorithm>
|
|
#include <cstddef>
|
|
#include <ctime>
|
|
#include <set>
|
|
#include <sstream>
|
|
|
|
std::vector<int> parseInput(int argc, char **argv) {
|
|
std::set<int> seen;
|
|
std::vector<int> result;
|
|
|
|
for (int i = 1; i < argc; ++i) {
|
|
std::istringstream iss(argv[i]);
|
|
int value;
|
|
if (!(iss >> value) || value < 0) {
|
|
throw std::runtime_error("Invalid input: " + std::string(argv[i]));
|
|
}
|
|
if (!seen.insert(value).second) {
|
|
throw std::runtime_error("Duplicate value: " +
|
|
std::string(argv[i]));
|
|
}
|
|
result.push_back(value);
|
|
}
|
|
return result;
|
|
}
|
|
|
|
template <typename Container> void printContainer(const Container &container) {
|
|
for (auto it = range(container)) {
|
|
std::cout << *it << " ";
|
|
}
|
|
std::cout << std::endl;
|
|
}
|
|
|
|
// Measure time and run sorting for vector and deque
|
|
void sortAndTime(std::vector<int> &vec, std::deque<int> &deq) {
|
|
auto vecStart = std::clock();
|
|
_fordJohnsonSort(vec);
|
|
auto vecEnd = std::clock();
|
|
|
|
auto deqStart = std::clock();
|
|
_fordJohnsonSort(deq);
|
|
auto deqEnd = std::clock();
|
|
|
|
std::cout << "After: ";
|
|
printContainer(vec);
|
|
|
|
double vecDuration = 1000000.0 * (vecEnd - vecStart) / CLOCKS_PER_SEC;
|
|
double deqDuration = 1000000.0 * (deqEnd - deqStart) / CLOCKS_PER_SEC;
|
|
|
|
std::cout << "Time to process a range of " << vec.size()
|
|
<< " elements with std::vector : " << vecDuration << " us"
|
|
<< std::endl;
|
|
|
|
std::cout << "Time to process a range of " << deq.size()
|
|
<< " elements with std::deque : " << deqDuration << " us"
|
|
<< std::endl;
|
|
}
|
|
|
|
std::vector<size_t> _generateJacobsthalOrder(size_t n) {
|
|
std::vector<size_t> sequence;
|
|
std::vector<bool> inserted(n, false);
|
|
|
|
// Generate the sequence
|
|
size_t j0 = 0, j1 = 1;
|
|
while (j1 < n) {
|
|
sequence.push_back(j1);
|
|
inserted[j1] = true;
|
|
size_t next = j1 + 2 * j0;
|
|
j0 = j1;
|
|
j1 = next;
|
|
}
|
|
for (size_t i = 0; i < n; ++i) {
|
|
if (!inserted[i])
|
|
sequence.push_back(i);
|
|
}
|
|
|
|
return sequence;
|
|
}
|
|
|
|
template <typename Container> void _fordJohnsonSort(Container &container) {
|
|
if (container.size() <= 1)
|
|
return;
|
|
|
|
Container mainChain;
|
|
Container pendingElements;
|
|
|
|
for (auto it = container.begin(); it != container.end();) {
|
|
int first = *it;
|
|
++it;
|
|
|
|
if (it != container.end()) {
|
|
int second = *it;
|
|
if (first > second) {
|
|
mainChain.push_back(first);
|
|
pendingElements.push_back(second);
|
|
} else {
|
|
mainChain.push_back(second);
|
|
pendingElements.push_back(first);
|
|
}
|
|
++it;
|
|
} else {
|
|
mainChain.push_back(first);
|
|
}
|
|
}
|
|
|
|
_fordJohnsonSort(mainChain);
|
|
|
|
std::vector<size_t> order = _generateJacobsthalOrder(pendingElements.size());
|
|
for (size_t i = 0; i < order.size(); ++i) {
|
|
_binaryInsert(mainChain, pendingElements[order[i]]);
|
|
}
|
|
container = mainChain;
|
|
}
|
|
|
|
template <typename Container> void _binaryInsert(Container &sorted, int value) {
|
|
typename Container::iterator itL = sorted.begin();
|
|
typename Container::iterator itH = sorted.end();
|
|
|
|
while (itL < itH) {
|
|
typename Container::iterator itMid = itL + (itH - itL) / 2;
|
|
if (*itMid < value)
|
|
itL = itMid + 1;
|
|
else
|
|
itH = itMid;
|
|
}
|
|
|
|
sorted.insert(itL, value);
|
|
}
|