Разный вывод каждый раз в с ++ (неожиданное поведение)

Question

это код для сортировки слиянием, и иногда он дает правильный вывод, но иногда он дает вывод, где изменяется одно значение.

#include "bits/stdc++.h"
using namespace std;

//function to merge two array
vector<int> merging(vector<int> a,vector<int> b){   
    int x = (int)a.size() + (int)b.size();
    vector<int> v(x);
    int p = 0;
    int q = 0;
    for(int i=0;i<x;++i){
        if((q<(int)b.size())?a[p]<b[q]:true && p<(int)a.size()){
            v[i] = a[p];
            p++;
        }else{
            v[i] = b[q];
            q++;
        }
    } 
    return v;
}


//splitting the array and then merging the array
vector<int> mergeSort(vector<int> k){
   int x = (int)k.size();
   if(x<2){
       return k;
   }
   vector<int> a(k.begin(),k.begin()+(x/2));
   vector<int> b(k.begin()+(x/2),k.end());
   return merging(mergeSort(a),mergeSort(b));
}


int main(){
    vector<int> v = {3,5,34,11,32,7,35,54,67,89,23,4,3};
    //calling the merge function
    vector<int> b = mergeSort(v);
    for(int i=0;i<(int)b.size();++i){
        cout << b[i] << "\n";
    }
  return 0;
}

иногда ожидается вывод 3 3 4 5 7 11 23 32 34 35 54 67 89

иногда вывод 3 3 4 5 7 11 23 32 34 -423887504 35 54 67

Answer 1

Ладно, сперва

if((q<(int)b.size())?a[p]<b[q]:true && p<(int)a.size()){

Yikes.

Это действительно запутанная логика c. У вас есть тройка внутри if, у вас есть true && ... (что то же самое, что и ...), и нигде нет абсолютно никакого промежутка, что делает все это еще более нечитаемым. Это не прошло бы ни одного обзора кода, который произошел в пределах 100 футов от меня. Еще до того, как я заглянул слишком далеко в ваш код, я догадался, что именно в этом проблема.

Итак, в вашем примере, когда вы попытаетесь объединить один раз в последний раз, вы получите следующие значения:

a = {35, 54, 67}
b = {3, 4, 23, 89}

Давайте пройдем через это с вашим слиянием ... Все хорошо для первых нескольких циклов, пока у вас не будет:

p = 3
q = 3
x = 7
i = 6
v = {3, 4, 23, 35, 54, 67, 0}

Теперь мы идем в l oop, i < x верно, поэтому мы все еще идем. И мы доберемся до вашего интереса, если

q < b.size() верно, 3 < 4. Итак, мы смотрим на a[p] < b[q] или a[3] < b[3]. Ой! Ты видишь проблему? a[3] вне диапазона. Это означает неопределенное поведение.

Вместо того, чтобы пытаться сделать все это в одном l oop, я бы попытался написать чистый код вместо короткого кода и использовать другой l oop. Этот l oop будет очищаться в зависимости от того, какой a или b вы оставили после того, как очистили другой (или, как я написал, это будут два цикла, из которых будет запущен только один) .

Это будет выглядеть так:

size_t p = 0, q = 0, i = 0;

while(p < a.size() && q < b.size()) {
    if(a[p] < b[q]) {
        v[i++] = a[p++];
    } else {
        v[i++] = b[q++];
    }
}

while(p < a.size()) {
    v[i++] = a[p++];
}

while(q < b.size()) {
    v[i++] = b[q++];
}

Вы заметите пару вещей, которые я здесь изменил:

• Я переехал из * От 1036 * до size_t, поэтому вы можете избежать всех этих уродливых приведений повсюду, поскольку ваши переменные уже будут соответствовать типу размеров вектора.
• Я разделил два цикла, чтобы освободить, какой бы из двух векторов еще не было имеет значения.
• Я перешел на while, так как я думаю, что они выглядят здесь лучше.

Answer 2

Несколько замечаний:

Операторское восприятие - ((q < b.size()) ? a[p] < b[q] : true && p < a.size()) эквивалентно: (q < b.size() ? a[p] < b[q] : p < a.size()). Обратите внимание, что вы не учитываете p, что, к сожалению, может быть более (неопределенное поведение). Обратите внимание, что это ваша ошибка. Исправление довольно простое -

(q < b.size() && p < a.size() ? a[p] < b[q] : p < a.size()) 

, которое применяет сравнение, только если в обоих массивах остались какие-либо элементы.

Более того, в вашем коде много плохих шаблонов:

Прежде всего, у вас есть много избыточных типов в стиле C. Это плохо по двум причинам: 1. Вы пишете на C ++, используйте приведения C ++! (static_cast в вашем случае) 2. Вы читаете без видимой причины. Существует очень веская причина, по которой тип размера в векторах (и обычно в C ++) равен std::size_t. Используйте это!

Еще одна вещь в вашем коде заключается в том, что вы передаете аргументы как значения, а не как const-ref, что является очень плохой практикой и приводит к ненужным копиям, происходящим вокруг.

В-третьих, ваше имена переменных не имеют смысла.

И в-четвертых, вы используете пространство имен std, что крайне не рекомендуется.

Answer 3

Может быть проблема в этой строке:

if((q<(int)b.size())?a[p]<b[q]:true && p<(int)a.size()){

Вы не проверяете размер массива 'a' перед использованием [p]. Так, иногда (из-за потери памяти) a [p] может быть меньше, чем b [q], иногда нет.

Как вариант, конечно. Давайте проверим размер массива перед использованием.