vendredi 4 janvier 2019

Divide and conquer merge sorting not working

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