Here is the code. I simply did a merge sorting using a Divide and Conquer algorithm but it doesn't work and i haven't found why. I'm passing an unordered vector, 0 and vector.size()
to the mergeSort
function.
template<typename T>
void mergeSort(std::vector<T>& vec, int left, int right)
{
int length = right - left;
if(length <= 3)
directInsertion(vec, left, right);
else
{
int middle = left + (length >> 1);
mergeSort(vec, left, middle);
mergeSort(vec, middle + 1, right);
merge(vec, left, middle , right);
}
}
template<typename T>
void merge (std::vector<T>& vec, int left, int middle, int right)
{
int length = right - left;
int p = left;
int q = middle + 1;
std::vector<T> tmp;
for(size_t l = 0; l < length; ++l)
{
if(p <= middle && (q > right || vec[p] <= vec[q]))
tmp.push_back(vec.at(p++));
else
tmp.push_back(vec.at(q++));
}
for(size_t l = 0; l < length; ++l)
vec[left + l] = tmp[l];
}
The directInsertion function is working properly that's why i didn't post it.
Aucun commentaire:
Enregistrer un commentaire