ошибка сегментации двойной рекурсии c ++ - PullRequest
Новая
       23

ошибка сегментации двойной рекурсии c ++

0 голосов
/ 03 июня 2018

Я недавно написал этот алгоритм сортировки быстрой сортировки.После компиляции я получаю "ошибку сегментации (ядро сброшено)".Я отладил его, и оказалось, что строка 25 вызывает проблему: v2 = quicksort (v2);Тем не менее, я не знаю, почему я получаю «ядро сброшено», так как я понятия не имею, в чем проблема с этой строкой.Вот мой код: 

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

using namespace std;

vector <float> quicksort(vector <float> Vec)
{
    if(Vec.size() > 1)
    {
        float pivot = Vec[(Vec.size())/2-1];

        vector <float> v1, v2;
        vector <float> V;

        for(unsigned int i = 0; i < Vec.size(); i++)
        {
            if(Vec[i] >= pivot)
                v2.push_back(Vec[i]);
            else
                v1.push_back(Vec[i]);
        }

        v1 = quicksort(v1);
        v2 = quicksort(v2);
        //after debuggung, I found out that the line above causes the "segmentation fault (core dumped)" (line 25)

        for(unsigned int i = 0; i < v1.size(); i++)
            V.push_back(v1[i]);
        for(unsigned int i = 0; i < v2.size(); i++)
            V.push_back(v2[i]);

        return V;
    }
    else
    {
        return Vec;
    }

}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    vector <float> v;

    for(int i = 0; i < 100; i++)
    {
        v.push_back(rand() % 100);
        cout << v[i] << " ";
    }

    v = quicksort(v);

    for(int i = 0; i < 100; i++)
    {
        cout << v[i] << " ";
    }

    return 0;
}

Спасибо за помощь.

Ответы [ 2 ]

0 голосов
/ 03 июня 2018

Переходит в переполнение стека.

Если ось является максимальным числом вектора Vec, его необходимо перетащить из Vinf в Vsup. 

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

using namespace std;

vector <float> quicksort(vector <float> Vec) {        //the int f was never used un the function
    if (Vec.size() > 1){
        vector <float> Vinf, Vsup, Vtmp;
        Vinf.push_back(Vec[(Vec.size()) / 2 - 1]);
        float pivot = Vinf[0];
        Vec.erase(Vec.begin() + Vec.size() / 2 - 1);
        for (unsigned int i = 0; i < Vec.size(); i++)
            Vec[i] > pivot ? Vsup.push_back(Vec[i]) : Vinf.push_back(Vec[i]);
        if (Vinf.size() == Vec.size() + 1) {
            Vsup.push_back(pivot);
            Vinf.erase(Vinf.begin());
        }
        Vinf = quicksort(Vinf);
        Vsup = quicksort(Vsup);
        for (unsigned int i = 0; i < Vinf.size(); Vtmp.push_back(Vinf[i++]));
        for (unsigned int i = 0; i < Vsup.size(); Vtmp.push_back(Vsup[i++]));
        return Vtmp;
    }
    else
        return Vec;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    vector <float> v;
    for (int i = 0; i < 100; cout << v[i++] << " ")
        v.push_back(rand() % 100);
    cout << endl;
    v = quicksort(v);
    for (int i = 0; i < v.size(); cout << v[i++] << " ");
    return 0;
}
0 голосов
/ 03 июня 2018

Прежде всего, чтобы получить абсолютно случайное число с помощью rand (), вам нужно запустить генератор чисел.Для этого вы включаете библиотеку «time.h», а затем пишете: srand (time(NULL));

Во-вторых, ваша быстрая сортировка принимает два параметра: вектор с именем Vec и int f, который ни для чего не используется.Возьмем int f параметров функции.

В-третьих, проблема в том, что в этой части кода происходит бесконечный цикл (строки с 17 по 23): 

for(unsigned int i = 0; i < Vec.size(); i++){
    if(Vec[i] >= pivot)
        v2.push_back(Vec[i]);
    else
        v1.push_back(Vec[i]);
}

Представьте, что нашВектор Vec равен {2, 3} (это были фактические значения, потому что мы не запустили генерацию случайных чисел).

То, что происходит, это то, что у нас есть pivot = 2, а затем мы говорим, чтоесли Vec [0], равное 2, больше или равно оси вращения, мы добавляем Vec [0] к v2, а затем то же самое для Vec [1], равным 3. Тогда это происходит бесконечно, потому что тогда вы говоритеv2 = quicksort(v2);.Это сделает Vec = v2.А это значит, что он никогда не станет меньше, потому что, опять же, Vec равен {2, 3}, и, следовательно, наш пивот = 2.

...