CODEWITHSUNDEEP
c++c++17
Reza Afra
Reza Afra

Reputation: 185

Assignment in C++ changes the numbers

I am writing quicksort and I get segfault. I tried the find the source of error and it seems in partition function when I assign i I get 15460 and for j I get -1. I could not figure out how that can happen.

#include <iostream>
#include <vector>
#include <random>
#include <algorithm>

int partition(std::vector<int>& A, int lo, int hi) {
    int i = lo;
    int j = hi + 1;
    while (true) {
        while (A[++i] < A[lo])
            if (i == hi) break;
        while (A[lo] < A[--j])
            if (j == lo) break;
        if (i >= j) std::swap(A[i], A[j]);
    }
    std::swap(A[lo], A[j]);
    return j;
}

void sort(std::vector<int>& A, int lo, int hi) {
    if (hi <= lo) return;
    int j = partition(A, lo, hi);
    sort(A, lo, j - 1);
    sort(A, j + 1, hi);
}

void sort(std::vector<int>& A) {
    std::random_device random_device;
    std::mt19937 rng(random_device());
    std::shuffle(std::begin(A), std::end(A), rng);
    sort(A, 0, A.size() - 1);
}

int main() {
    std::vector<int> V = {2, 1};
    sort(V);
    for (const auto& item: V) std::cout << item;
}

Upvotes: 0

Views: 85

Answers (1)

SKCoder
SKCoder

Reputation: 429

In your function partition() you have nested while loops. The outer one never quits, as mentioned by 1201ProgramAlarm. The two inner loops keep in-/decrementing i/j. As the ++i/--j is done at least once for every run of the outer while loop, those values will eventually leave the valid range for accessing the array. And as those indices are used for accessing the array, you inescapable will get that segfault.

Upvotes: 1

Related Questions