profile
Размещено 4 года назад по предмету Информатика от stasf01

Требуется отсортировать массив по неубыванию, используя сортировку слиянием.

Чтобы убедиться, что действительно используется сортировка слиянием, после каждого осуществленного слияния (то есть, когда соответствующий подмассив уже отсортирован!), требуется вывести индексы граничных элементов и их значения.

  1. Ответ на вопрос
    Ответ на вопрос дан Вованичикчка

    Код, который необходимо добавить, выделен на прикрепленной картинке красным прямоугольником.

    Замечание: везде в коде не указан тип у vector. Необходимо указать тип, например vector<int>. В прикрепленном коде все исправлено.

    Весь листинг:

    #include <iostream>

    #include <vector>

    using namespace std;

    vector<int> merge(vector<int> &A, vector<int> &B) {

       int i = 0;

       int j = 0;

       vector<int> C(A.size() + B.size());

       for (int k = 0; k < C.size(); k++) {

           // Если в массиве А все элементы закончились

           if (i == A.size()) {

               C[k] = B[j];

               j++;

               // Если в массиве B все элементы закончились

           } else if (j == B.size()) {

               C[k] = A[i];

               i++;

           } else if (A[i] <= B[j]) {

               C[k] = A[i];

               i++;

           } else {

               C[k] = B[j];

               j++;

           }

       }

       return C;

    }

    vector<int> merge_sort(vector<int> &V, int l, int r) {

       // Проверяем, не равна ли длина 1

       // Частный случай, при котором рекурсия завершается

       if (r - l == 1) {

           vector<int> res(1);

           res[0] = V[l];

           return res;

       }

       

       // Находим середину массива

       int m = (l + r) / 2;

       

       // Сортируем левую и правую половины независимо

       vector<int> left = merge_sort(V, l, m);

       vector<int> right = merge_sort(V, m, r);

       

       cout << l + 1 << ' '

           << r << ' '

           << right.front() << ' '

           << left.back() << endl;

       // Сливаем отсортированные половины

       return merge(left, right);

    }

    int main(){

       

       int n;

       cin >> n;

       vector<int> v(n);

       for (int i = 0; i < n; i++) {

           cin >> v[i];

       }

       

       // Вызов сортировки

       vector<int> v_sorted = merge_sort(v, 0, v.size());

       // Вывод результата

       for (int i = 0; i < v.size(); i++) {

           cout << v_sorted[i] << ' ';

       }

       return 0;

    }

Не тот ответ на вопрос, который вам нужен?
Найди верный ответ
Самые новые вопросы
tegysigalpa2012
Русский язык - 5 лет назад

Помогите решить тест по русскому языку тест по русскому языку «местоимение. разряды местоимений» для 6 класса 1. укажите личное местоимение: 1) некто 2) вас 3) ни с кем 4) собой 2. укажите относительное местоимение: 1) кто-либо 2) некоторый 3) кто 4) нам 3. укажите вопросительное местоимение: 1) кем-нибудь 2) кем 3) себе 4) никакой 4. укажите определительное местоимение: 1) наш 2) который 3) некий 4) каждый 5. укажите возвратное местоимение: 1) свой 2) чей 3) сам 4) себя 6. найдите указательное местоимение: 1) твой 2) какой 3) тот 4) их 7. найдите притяжательное местоимение: 1) самый 2) моего 3) иной 4) ничей 8. укажите неопределённое местоимение: 1) весь 2) какой-нибудь 3) любой 4) этот 9. укажите вопросительное местоимение: 1) сколько 2) кое-что 3) она 4) нами 10. в каком варианте ответа выделенное слово является притяжательным местоимением? 1) увидел их 2) её нет дома 3) её тетрадь 4) их не спросили

Информация

Посетители, находящиеся в группе Гости, не могут оставлять комментарии к данной публикации.