Возникли проблемы, которые Mergesort сравнивает и упорядочивает (c ++) - PullRequest
Новая
       9

Возникли проблемы, которые Mergesort сравнивает и упорядочивает (c ++)

1 голос
/ 18 марта 2019

Я прочитал и понял, как работает Mergesort (как текст), и теперь я пытаюсь его кодировать.Я закончил ту часть, где вы делите данные (я использую векторы) до тех пор, пока они не получат каждый размер 1. Теперь я написал код для другой необходимой части в Mergesort, я не знаю, как это назвать, но я просто называю это "сравнить и упорядочить часть ".

У вас есть 2 вектора, и эта часть должна сравнить самые первые элементы, взять меньший элемент, затем удалить выбранный элемент и поместить его в новый вектор.Делая это, пока оба вектора не будут иметь размер 0.

Извините за длинный код, но я действительно не понимаю, почему последний элемент игнорируется кодом?: / Я добавил несколько комментариев, так что, возможно, легче следовать тому, что я пытался сделать.

Я пробовал как вход : 

vector<int> v1 = {1,4,5,9};
vector<int> v2 = {2,3,6,7,8};

Выход : 

1 2 3 4 5 6 7 8 0

vector<int> sortit(vector<int> &left, vector<int> &right) {
    vector<int> sorted(left.size() + right.size());
    int i = 0;
    while (left.size() > 0 && right.size() > 0) {
        if (left.at(0) <= right.at(0)) {
            sorted.at(i) = left.at(0);      // putting the smaller element into the new vector
            left.erase(left.begin());       // removing this smaller element from the (old) vector
        }
        else if (right.at(0) <= left.at(0)) {
            sorted.at(i) = right.at(0);     // see comment above
            right.erase(right.begin());     // see comment above
        }
        else if (left.size() <= 0 && right.size() > 0) {    // if left vector has no elements, then take all elements of the right vector and put them into the new vector
            while (right.size() > 0) {
                sorted.at(i) = right.at(0);
                right.erase(right.begin());
            }
        }
        else if (right.size() <= 0 && left.size() > 0) {    // the same just for the right vector
            while (left.size() > 0) {
                sorted.at(i) = left.at(0);
                left.erase(left.begin());
            }
        }
        i++;
    }
    return sorted;
}

Ответы [ 3 ]

2 голосов
/ 18 марта 2019

Проверка того, что один из массивов исчерпан, а другой массив имеет оставшиеся элементы, должна находиться вне основного цикла while.Итак, попробуйте поставить две нижеуказанные проверки за пределами. 

else if (left.size() <= 0 && right.size() > 0)    

else if (right.size() <= 0 && left.size() > 0)

Подумайте о том, что произойдет, когда один массив имеет (1), а другой (2,3). При добавлении 1 к отсортированному вектору, while(left.size() > 0 && right.size() > 0) условие ложно и цикл прерывается.Поэтому остальные элементы игнорируются.

1 голос
/ 18 марта 2019

Код можно упростить: 

vector<int> sortit(vector<int> &left, vector<int> &right) {
    vector<int> sorted(left.size() + right.size());
    int i = 0;
    while (1) {
        if (left.at(0) <= right.at(0)) {
            sorted.at(i++) = left.at(0);
            left.erase(left.begin());
            if(left.size == 0){
                do{
                    sorted.at(i++) = right.at(0);
                    right.erase(right.begin());
                }while(right.size != 0);
                return;
            }
        } else {
            sorted.at(i++) = right.at(0);
            right.erase(right.begin());
            if(right.size == 0){
                do{
                    sorted.at(i++) = left.at(0);
                    left.erase(left.begin());
                }while(left.size != 0);
                return;
            }
        }
    }
    return sorted;
}

вместо стирания элементов векторов можно использовать индексацию: 

vector<int> sortit(vector<int> &left, vector<int> &right) {
    vector<int> sorted(left.size() + right.size());
    int i = 0;
    int ll = 0;
    int rr = 0;
    while (1) {
        if (left[ll] <= right[rr]) {
            sorted[i++] = left[ll++];
            if(ll == left.size){
                do{
                    sorted[i++] = right[rr++];
                }while(rr != right.size);
                break;
            }
        } else {
            sorted[i++] = right[rr++];
            if(rr == right.size){
                do{
                    sorted[i++] = left[ll++];
                }while(ll != left.size);
                break;
            }
        }
    }
    return sorted;
}
1 голос
/ 18 марта 2019

не знаю, как назвать ['] "сравнить и упорядочить часть"

Условно: объединить

извинитедля длинного кода

используйте 

first = *left <= *right ? left : right

и манипулируйте этим, избегая репликации кода.

не понимаю, почему самый последний элементигнорируется кодом?

left.at(0) <= right.at(0)

и 

right.at(0) <= left.at(0)

охватывают все возможные результаты сравнения (равенство дважды): дальнейшее вычисление else не выполняется.
Перемещение «движущихся частей»чтобы следовать «правильному слиянию» как , предложенному Msk , обратите внимание, что предварительные проверки не требуются - просто используйте «петли перемещения».

О вашем коде можно многое сказать (начиная с комментария) - см. обзоры кода реализации слияния C ++ для идей.
Если вы хотите, чтобы код находился вконтроль рассмотрен на CR @ SE, обязательно наберите по теме и , напишите Хороший вопрос .

...