dimanche 21 janvier 2018

What is wrong with this quicksort implementation

I have tried implementing quicksort for the first time. However, my recursive quickSort function goes into an infinite loop, and I can't find the logical flaw in my code:

std::vector<int> quickSort(const std::vector<int> &v) {
    int pivot = v[v.size() / 2];
    std::vector<int> chunk1, chunk2;

    for (const auto &a : v) {
        (a <= pivot ? chunk1 : chunk2).push_back(a);
    }

    if (chunk1.size() > 1) chunk1 = quickSort(chunk1);
    if (chunk2.size() > 1) chunk2 = quickSort(chunk2);
    chunk1.insert(chunk1.end(), chunk2.begin(), chunk2.end());
    return chunk1;
}

Aucun commentaire:

Enregistrer un commentaire