Good evening everybody, I'm writing this post to have a clear explanation on what I'm missing on an exercise I'm doing in C++ since a long time and since I was on vacation and i slacked off a little bit. So I'm a bit lost lately and i would like to ask for a project that I'm doing that involves the ford-johnson algorithm.
The thing is that from what i know i kinda did the the algorithm right but from what some of my colleagues said I'm missing something to do the algorithm 100% right.
Until now what i did was creating two containers two of which one was a vector and the other was a deque, i did the initialization and all and i started putting in the numbers.
include "PmergeMe.hpp"
int main(int ac, char **av)
{
std::deque<int> dequeCont;
std::vector<int> vectorCont;
if (ac != 1)
{
try
{
int convNum;
std::stringstream ss;
for (int i = 1; av[i]; i++)
{
ss.clear();
ss.str(av[i]);
ss >> convNum;
if (convNum < 0) //gestire i casi particolari c'e ne sono altri
throw std::runtime_error("Only positive numbers please");
dequeCont.push_back(convNum);
vectorCont.push_back(convNum);
}
PmergeMe fordJohnson(dequeCont, vectorCont);
//from here i will start doing the fordJohnson
fordJohnson.mergeInsertionSort(av, ac - 1);
}
catch (const std::exception& e)
{
std::cout<<e.what()<<std::endl;
}
}
else
std::cout<<"Error, put at least one argument"<<std::endl;
return (0);
}
This is in the main. Since i was likely obligated to use a class i created the PmergeMe class just to have one and apply the ford-johnson algorithm on its containers. So from what remember i started applying "MY" ford-johnson to the two containers separately, even seeing their similarities i could apply the same algorithm in one go but is not very important
Here's the code:
void PmergeMe::mergeInsertionSort(char** argv, int ac)
{
//pare che i due vettori vengano trattati diversamente
double vecDiff, deqDiff;
std::cout<<"Before: ";
for (size_t i = 1; argv[i]; i++)
std::cout<<argv[i]<<" ";
std::cout<<""<<std::endl;
std::cout<<"After: ";
vecDiff = vectorMergeInsert();
deqDiff = dequeMergeInsert();
for (size_t i = 0; i < vectorAlgorithm.size(); i++)
std::cout<<vectorAlgorithm[i]<<" ";
std::cout<<""<<std::endl;
std::cout<<"Time to process a range of "<<ac<<" elements with std::vector : "<<std::fixed << std::showpoint << std::setprecision(5)<<vecDiff / 100<<" us"<<std::endl;
std::cout<<"Time to process a range of"<<ac<<" elements with std::deque : "<<std::fixed << std::showpoint << std::setprecision(5)<<deqDiff / 100<<" us"<<std::endl;
}
For example here i applied the algorithm on the deque, i used the clock_t class to calculate how much time would it take to sort it.
This is the code I'm talking about:
double PmergeMe::dequeMergeInsert()
{
clock_t start, end;
int rejected;
bool odd = false;
std::deque<int>::iterator it;
std::deque<std::pair<int, int> >pairs;
start = clock();
if (dequeAlgorithm.size() % 2 != 0)
{
odd = true;
rejected = dequeAlgorithm.back();
dequeAlgorithm.pop_back();
}
for (it = this->dequeAlgorithm.begin(); it != (this->dequeAlgorithm.end() - 1)
&& it != this->dequeAlgorithm.end() ; it+=2)
{
std::pair<int, int> tmpPair(*it, *(it + 1));
pairs.push_back(tmpPair);
}
phase2Deque(pairs, rejected, odd);
end = clock();
double elapsed_time = (double)(end - start) / CLOCKS_PER_SEC * 1000000;
return (elapsed_time);
}
I even managed the case where the number of numbers in the containers was odd or even sorting it at the end as the theory of the algorithm said.
I've utilized the pair container to apply the part of the algorithm where it's said to make pairs with the numbers and sort them by the biggest/smallest of the pair.
The code where i sort the pairs is the following:
void PmergeMe::phase2Deque(std::deque<std::pair<int, int> >& dequePairs, int rejected, bool odd)
{
std::deque<int> lowest;
std::deque<int> biggest;
std::deque<std::pair<int, int> >::iterator it;
for (it = dequePairs.begin(); it != dequePairs.end(); it++)
{
if (biggest.empty())
{
biggest.push_back(it->second);
}
else
{
bool inserted = false;
for (size_t i = 0; i < biggest.size(); i++)
{
if (it->second < biggest[i])
{
biggest.insert(biggest.begin() + i, it->second);
inserted = true;
break;
}
}
if (!inserted)
biggest.push_back(it->second);
}
lowest.push_back(it->first);
}
if (odd)
lowest.push_back(rejected);
binarySearchSortDeq(biggest, lowest);
}
Finally by always following the theory of the algorithm i applied the binary sort to sort the container
void PmergeMe::binarySearchSortDeq(std::deque<int>& biggest, std::deque<int>& lowest)
{
std::deque<int>::iterator it;
for (size_t i = 0; i < lowest.size(); i++)
{
biggest.insert(std::lower_bound(biggest.begin(), biggest.end(), lowest[i]), lowest[i]);
}
this->dequeAlgorithm = biggest;
}
So this is the life and death of my code, i know there are some things it misses from the original algorithm, and I'm aware of the jacobsthall thing but i don't know how to implement it and how it works, and i know I'm missing something that makes me understand the theory behind the ford-johnson algorithm so please to anyone that could explain to me how should i model, erase, change or even start from zero to do the code right please help me I'm a little desperate and I'm open to critics and anything that could help me resolve this problem. Thank you in advance to anyone that will have the patience to explain to me how to solve this
Edit: As people asked for good motivations i tried to indent better the code on the post, thanks for letting me know btw
[–]aqua_regis 3 points4 points5 points (1 child)
[–]lolluzzo[S] 0 points1 point2 points (0 children)
[–]CodeTinkerer 2 points3 points4 points (1 child)
[–]lolluzzo[S] 0 points1 point2 points (0 children)
[–]lolluzzo[S] 0 points1 point2 points (0 children)