recursion - Recursive mergeSort to Iterative in c++ using deque -
i'm trying iterative version of multiple recursive mergesort:
i need make iterable sort function:
template<class t> deque<t> mergesort<t>::sort(deque<t> &right){ int size = right.size(); if (size <= 1){ return right; } int middle = size/2; deque<t> left; for(int = 0; < middle; i++){ left.push_back(right.front()); right.pop_front(); } left = sort(left); right = sort(right); return merge(left, right); }
the merge function can same:
template<class t> deque<t> mergesort<t>::merge(deque<t> &left, deque<t> &right){ deque<t> result; while(left.size() > 0 || right.size() > 0){ if (left.size() > 0 && right.size() > 0){ if (getorder(left.front(),right.front())){ result.push_back(left.front()); left.pop_front(); } else{ result.push_back(right.front()); right.pop_front(); } } else if(left.size() > 0){ result.push_back(left.front()); left.pop_front(); } else if(right.size() > 0){ result.push_back(right.front()); right.pop_front(); } } return result; }
it's hard me make tranformation of multiple recursive function iterative function.
thanks everyvody , kind regards.
do have use dequeue? iterative version of merge sort called bottom-up merge sort. there's no need store information.
Comments
Post a Comment