0 / 0 / 0
Регистрация: 19.11.2015
Сообщений: 2
1

Слияние двух отсортированных массивов в третий

18.12.2018, 13:52. Показов 9955. Ответов 4

Author24 — интернет-сервис помощи студентам
Здравствуйте всем! Только начинаю изучать языки программирования. Помогите найти ошибку.
Необходимо создать два массива, слить и отсортировать их в третьем. Я написала сортировку двух массивов и даже смогла их слить. Вот код:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <iostream>
using namespace std;
//функция, сливающая массивы
void Merge(int *A, int first, int last, int *B, int first_1, int last_1) 
{
int middle, start, final, j, middle_1, start_1, final_1, k;
int *mas=new int[100],*mas_1=new int[100]; 
// Начало массива А.
middle=(first+last)/2; //вычисление среднего элемента A
start=first; //начало левой части A
final=middle+1; //начало правой части A
for(j=first; j<=last; j++) //выполнять от начала до конца A
if ((start<=middle) && ((final>last) || (A[start]<A[final])))
{
mas[j]=A[start];
start++;
}
else
{
mas[j]=A[final];
final++;
} // Конец массива А.
// Начало массива В.
middle_1=(first_1+last_1)/2; //вычисление среднего элемента В
start_1=first_1; //начало левой части В
final_1=middle_1+1; //начало правой части В
for(k=first_1; k<=last_1; k++) //выполнять от начала до конца В
if ((start_1<=middle_1) && ((final_1>last_1) || (B[start_1]<B[final_1])))
{
mas_1[k]=B[start_1];
start_1++;
}
else
{
mas_1[k]=B[final_1];
final_1++;
} // Конец массива В.
 
//возвращение результата в список
for (j=first; j<=last; j++) A[j]=mas[j];
for (k=first_1; k<=last_1; k++) B[k]=mas_1[k];
delete[]mas; delete[]mas_1; 
};
//рекурсивная процедура сортировки
void MergeSort(int *A, int first, int last, int *B, int first_1, int last_1)
{
{
if (first<last, first_1<last_1)
{
MergeSort(A, first, (first+last)/2, B, first_1, (first_1+last_1)/2); 
MergeSort(A, (first+last)/2+1, last, B, (first_1+last_1)/2+1, last_1);
Merge(A, first, last, B, first_1, last_1); //слияние двух частей
}
}
};
//главная функция
void main()
{
setlocale(LC_ALL, "Rus");
int n, m, i, l, q; int p=0;
int *A=new int[100], *B=new int[100], *C=new int[100];
cout<<"Размер массива A > "; cin>>n;
cout<<"Размер массива B > "; cin>>m;
cout<<"Размер массива С > "; q=n+m; cout<<q<<endl;
for (i=1; i<=n; i++)
{ cout<<i<<" элемент A > "; cin>>A[i];}
for (l=1; l<=m; l++)
{ cout<<l<<" элемент B > "; cin>>B[l];}
 
MergeSort(A, 1, n, B, 1, m); //вызов сортирующей процедуры
cout<<"Упорядоченный массив A: "; //вывод упорядоченного массива A
for (i=1; i<=n; i++) cout<<A[i]<<" "; 
cout<<endl;
cout<<"Упорядоченный массив B: "; //вывод упорядоченного массива B
for (l=1; l<=m; l++) cout<<B[l]<<" ";
cout<<endl;
cout<<"Упорядоченный массив C: "; //вывод упорядоченного массива C
for (i=0; i<=n; i++) {for (l=0; l<=m; l++) 
    while (p<n+m) {if (A[i]<B[l]) C[p++]=A[i++];
    else C[p++]=B[l++];}}
 
for (p=0; p<=q; p++) cout<<C[p]<<" ";
cout<<endl;
delete[]A; delete[]B; delete[]C;
system("pause");
};
Но в консоли частично выдается чушь:

Код
Размер массива A > 3
Размер массива B > 3
Размер массива С > 6
1 элемент A > 5
2 элемент A > 6
3 элемент A > 2
1 элемент B > 3
2 элемент B > 8
3 элемент B > 2
Упорядоченный массив A: 2 5 6
Упорядоченный массив B: 2 3 8
Упорядоченный массив C: -842150451 -842150451 2 2 3 5 -842150451

Помогите найти ошибку.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
18.12.2018, 13:52
Ответы с готовыми решениями:

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

Провести слияние двух массивов по возрастанию, создавая третий массив
Провести слияние двух массивов по возрастанию, создавая третий массив. Помогите пожалуйста:(

Из двух отсортированных по возрастанию массивов сформировать третий, отсортированный также по возрастанию
Нужно написать программу с тремя массивами :| Из двух отсортированных по возрастанию массивов...

Слияние отсортированных массивов.
задача: есть двумерный целочисленный массив n на n в котором каждая строка отсортирована по...

4
Мозгоправ
1744 / 1038 / 468
Регистрация: 01.10.2018
Сообщений: 2,138
Записей в блоге: 2
18.12.2018, 17:20 2
Во-первых, перемудрили. Во-вторых, напутали.
Запомните, в C/C++ нумерация элементов массива начинается с 0. Если количество элементов N, то последний элемент массива имеет индекс N-1.

Код поправил.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <iostream>
using namespace std;
//функция, сливающая массивы
void Merge(int *A, int first, int last, int *mas) {
    int middle, part1, part2, j;
    // Начало массива А.
    middle = (first + last) / 2; //вычисление среднего элемента A
    part1 = first; //начало левой части A
    part2 = middle; //начало правой части A
    for (j = first; j < last; j++) {    //выполнять от начала до конца A
        if (part1 >= middle) {
            mas[j] = A[part2++];
            continue;
        }
        if (part2 >= last) {
            mas[j] = A[part1++];
            continue;
        }
        if (A[part1] < A[part2])
            mas[j] = A[part1++];
        else
            mas[j] = A[part2++];
    }
 
    //возвращение результата в список
    for (j = first; j < last; j++) A[j] = mas[j];
};
//рекурсивная процедура сортировки
void _MergeSort(int *A, int first, int last, int *mas) {
    {
        if (last - first > 1) {
            _MergeSort(A, first, (first + last) / 2, mas);
            _MergeSort(A, (first + last) / 2, last, mas);
            Merge(A, first, last, mas); //слияние двух частей
        }
    }
};
//нерекурсивная процедура сортировки
void MergeSort(int *A, int first, int last) {
    int *_mas = new int[100];       // используем для слияния постоянный буфер
    _MergeSort(A, first, last, _mas);
    delete[] _mas;
}
//главная функция
int main() {
    setlocale(LC_ALL, "Rus");
    int n, m, i, l, q; int p = 0;
    int *A = new int[100], *B = new int[100], *C = new int[100];
    cout << "Размер массива A > "; cin >> n;
    cout << "Размер массива B > "; cin >> m;
    cout << "Размер массива С > "; q = n + m; cout << q << endl;
    for (i = 0; i < n; i++) {
        cout << i << " элемент A > "; cin >> A[i];
    }
    for (l = 0; l < m; l++) {
        cout << l << " элемент B > "; cin >> B[l];
    }
 
    MergeSort(A, 0, n); //вызов сортирующей процедуры
    MergeSort(B, 0, m); //вызов сортирующей процедуры
    cout << "Упорядоченный массив A: "; //вывод упорядоченного массива A
    for (i = 0; i < n; i++) cout << A[i] << " ";
    cout << endl;
    cout << "Упорядоченный массив B: "; //вывод упорядоченного массива B
    for (l = 0; l < m; l++) cout << B[l] << " ";
    cout << endl;
    cout << "Упорядоченный массив C: "; //вывод упорядоченного массива C
 
    i = l = 0;
    for (int j = 0; j < q; ++j) {
        if (i >= n) {       // массив A уже весь обработан
            C[j] = B[l++];
            continue;
        }
        if (l >= m) {       // массив B уже весь обработан
            C[j] = A[i++];
            continue;
        }
        if (A[i] < B[l])
            C[j] = A[i++];
        else
            C[j] = B[l++];
    }
 
 
    for (p = 0; p < q; p++) cout << C[p] << " ";
    cout << endl;
    delete[]A; delete[]B; delete[]C;
    system("pause");
}
Внеплановая оптимизация: выделение памяти под временный массив вынес из Merge, что бы при каждм слиянии не дёргать менеджер памяти.

Добавлено через 1 минуту
Там ещё можно кое-что изменить. Но я не стал ваш код переписывать полностью.
2
1352 / 851 / 365
Регистрация: 26.02.2015
Сообщений: 3,799
18.12.2018, 17:31 3
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <algorithm>
#include <array>
#include <iostream>
#include <random>
 
int main() {
 
    constexpr std::size_t size = 10;
 
    std::array<int, size> arrA;
    std::array<int, size> arrB;
    std::array<int, size * 2> arrC;
 
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<int> dist(-50, 50);
 
    std::generate(arrA.begin(), arrA.end(), [&gen, dist]() { return dist(gen); });
    std::generate(arrB.begin(), arrB.end(), [&gen, dist]() { return dist(gen); });
 
    std::sort(arrA.begin(), arrA.end());
    std::sort(arrB.begin(), arrB.end());
 
    std::merge(arrA.begin(), arrA.end(), arrB.begin(), arrB.end(), arrC.begin());
 
    std::copy(arrC.begin(), arrC.end(), std::ostream_iterator<int>(std::cout, " "));
 
    system("PAUSE");
    return 0;
 
}
0
0 / 0 / 0
Регистрация: 19.11.2015
Сообщений: 2
19.12.2018, 09:37  [ТС] 4
Спасибо Вам большое, L0M, за упрощение кода и помощь! И все же, не могли бы подсказать в чем была ошибка вывода? В индексах? Т.е. если я исправлю 1 на 0, то и мой код верно сработает?

Добавлено через 2 минуты
Спасибо все за ответы.)
0
Мозгоправ
1744 / 1038 / 468
Регистрация: 01.10.2018
Сообщений: 2,138
Записей в блоге: 2
20.12.2018, 01:27 5
Loue, нет, ваш код верно не сработает при исправлении только индексации массивов. Если вы заметили, то ваш код претерпел достаточно большие изменения, что бы он заработал как надо. Разберитесь как работает мой вариант и сравните с тем, как должен был бы работать ваш вариант в вашем представлении. Думаю, что разберётесь где и что вы сделали не так.
0
20.12.2018, 01:27
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
20.12.2018, 01:27
Помогаю со студенческими работами здесь

Слияние двух отсортированных списков
Напишите функцию List&amp; merge(List&amp; L1, List&amp; L2), добавляю- щую к упорядоченному списку L1 также...

Слияние двух векторов в третий по условию
Здравствуйте, подскажите пожалуйста как написать сравнение двух массивов (массив старых и массив...

Слияние двух массивов
Всем привет. Возникла проблема с задачей. Даны два массива одинакоого размера. Нужно создать 3...

Слияние двух динамических массивов…
Приветствую Вас!:) Задача такая: Даны два массива: A и B (числовые), упорядоченные по...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru