Ошибка выполнения C ++ реализации сортировки слиянием - PullRequest
Новая
       33

Ошибка выполнения C ++ реализации сортировки слиянием

1 голос
/ 14 мая 2019

Итак, я работал над проблемами в Leetcode, 912. Это настолько просто, насколько это может быть проблема - сортировка массива в порядке возрастания.Я просто делаю это, чтобы пройтись по всем алгоритмам сортировки.Однако, когда дело доходит до сортировки слиянием, я написал этот алгоритм, и он показывает ошибку времени выполнения, как показано ниже.Прошло несколько простых тестовых случаев с 6 или 10 целыми числами.но ошибка времени выполнения возникает, когда дело доходит до гораздо более длинного контрольного примера.Кто-нибудь знает, какая часть моего кода может вызвать это?Большое спасибо заранее! 

void mergesort(vector <int> &nums) {
    int length=nums.size();
    if (length<2)
    {
        return ;
    }
    int mid= length/2;
    vector <int> left;
    vector <int> right;
    for (int x=0;x<mid;x++)
    {
        left.push_back(nums[x]);
    }
    for (int y=0;y<length-mid;y++)
    {
        right.push_back(nums[y+mid]);
    }
    mergesort(left);
    mergesort(right);
    merge(left,right,nums);

}
void merge(vector <int>& left,vector <int>& right,vector <int>& nums){
    int i,j,count {0};
    int l1=left.size();
    int l2=right.size();
        while (i<l1&&j<l2)
        {
            if (left[i]<right[j])
            {
                nums[count]=left[i];
                count++;
                i++;
            }
            else
            {
                nums[count]=right[j];
                count++;
                j++;
            }
        }
        while (i<l1)
        {
            nums[count]=left[i];
            count++;
            i++;
        }
        while (j<l2)
        {
            nums[count]=right[j];
            count++;
            j++;
        }
}
vector<int> sortArray(vector<int>& nums){
    mergesort(nums);
    return nums;
}

Я прошел тестовый пример как: [5,2,3,1], но для намного более длинного векторного ввода: я получил сообщение об ошибке времени выполнения: AddressSanitizer: SEGV on unknownадрес 0x61eff7f80674 (шт. 0x000000418d91 б.п. 0x7fff0f0847c0 sp 0x7fff0f0845a0 T0)

1 Ответ

2 голосов
/ 14 мая 2019

Вы не инициализируете i или j: 

 int i,j,count {0};

Это только инициализирует count в 0.Включите или прочитайте предупреждения вашего компилятора, так как он скажет вам об этом.

Измените это на: 

int i{0};
int j{0};
int count{0};
...