1

Тема: Злиття масивів

Дано два довільні одновимірні масиви дійсних чисел М1 і М2. Сформувати злиттям цих масивів упорядкований масив М3.
Що таке злиття??? Всюди де я шукав це поняття говориться тільки про сортування масивів. Поясніть, що це таке, бо я не розумію, що мені кодувати.

2

Re: Злиття масивів

grinyuk309 написав:

Дано два довільні одновимірні масиви дійсних чисел М1 і М2. Сформувати злиттям цих масивів упорядкований масив М3.

Загалом без сортування це не можливо.

grinyuk309 написав:

Що таке злиття?

Створення одного відсортованого масиву на основі кількох відсортованих масивів.

3

Re: Злиття масивів

може щосмь типу join /concatenate?

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

>>> a = np.array([[1, 2], [3, 4]])
>>> b = np.array([[5, 6]])
>>> np.concatenate((a, b), axis=0)
array([[1, 2],
       [3, 4],
       [5, 6]])
>>> np.concatenate((a, b.T), axis=1)
array([[1, 2, 5],
       [3, 4, 6]])
>>> np.concatenate((a, b), axis=None)
array([1, 2, 3, 4, 5, 6])

4 Востаннє редагувалося ping (06.12.2019 20:07:16)

Re: Злиття масивів

leofun01 написав:
grinyuk309 написав:

Дано два довільні одновимірні масиви дійсних чисел М1 і М2. Сформувати злиттям цих масивів упорядкований масив М3.

Загалом без сортування це не можливо.

grinyuk309 написав:

Що таке злиття?

Створення одного відсортованого масиву на основі кількох відсортованих масивів.

а чому відсортованих?
це вроді окремо - злиття, окремо - сортування

Подякували: leofun011

5

Re: Злиття масивів

ping написав:
leofun01 написав:

Створення одного відсортованого масиву на основі кількох відсортованих масивів.

а чому відсортованих?
це вроді окремо - злиття, окремо - сортування

Вірно. Але ж ТС хоче отримати упорядкований масив. А злиття довільних масивів дає довільний масив.

6

Re: Злиття масивів

leofun01 написав:
ping написав:
leofun01 написав:

Створення одного відсортованого масиву на основі кількох відсортованих масивів.

а чому відсортованих?
це вроді окремо - злиття, окремо - сортування

Вірно. Але ж ТС хоче отримати упорядкований масив. А злиття довільних масивів дає довільний масив.

вірно.  хоча не зовсім довільний.
завжди буде порядок слідування елементів який відображає порядок, що був у масивах які зливаються + порядок масивів, що зливаються.
тому задачу слід розбити на дві окремі частини:
- злиття масивів ( увапатку тс - вони одновимірні, тому на виході буде одновимірний масив)
- сортування (згідно умови - невідомо по якому критерію - зростання, спадання, спершу прості числа, спершу цілі , потім з плаваючою комою , і т.п.)

Подякували: leofun011

7

Re: Злиття масивів

ping написав:

задачу слід розбити на дві окремі частини:
- злиття
- сортування

Ем... Ну так і я про то.

8 Востаннє редагувалося ping (06.12.2019 21:20:10)

Re: Злиття масивів

leofun01 написав:
ping написав:

задачу слід розбити на дві окремі частини:
- злиття
- сортування

Ем... Ну так і я про то.

не зовсім )
Ви спершу сортували масиви, поттіми зливали

Створення одного відсортованого масиву на основі кількох відсортованих масивів.

можливо - технічна описка

Подякували: leofun011

9

Re: Злиття масивів

ping написав:

не зовсім )

Тепер я зрозумів. Ви пропонуєте спочатку злити і потім відсортувати. Це теж рішення.
Я про це навіть не подумав, бо мені завжди здавалося, що
T(A) + T(B) < T(A + B)
для будь-якого вибраного методу сортування, де T - час сортування масиву, { A, B } - розміри масивів.

10 Востаннє редагувалося ping (06.12.2019 21:46:42)

Re: Злиття масивів

Так масиви можуть пересікатися.тобто кінцевого сортування не уникнути.

Подякували: leofun011

11

Re: Злиття масивів

Я допустив помилку припустивши, що вони не перетинаються, визнаю. В таких мовах як { C, C++ } це дуже важливо.

12

Re: Злиття масивів

leofun01 написав:
grinyuk309 написав:

Дано два довільні одновимірні масиви дійсних чисел М1 і М2. Сформувати злиттям цих масивів упорядкований масив М3.

Загалом без сортування це не можливо.

grinyuk309 написав:

Що таке злиття?

Створення одного відсортованого масиву на основі кількох відсортованих масивів.

Окей, але в мене немає ніяких критеріїв для сортування, що мені тоді зливати?

13

Re: Злиття масивів

"Злиття масивів" узагалі означає просто створення масиву, який містить ті ж елементи, що й масиви, які зливають. Тобто об'єднання.
Є метод сортування масиву злиттям - масив ділиться на маленькі підмасиви (кінець-кінцем - розміру 1, які впорядковані за визначенням), які потім зливають зі збереженням впорядкованості.

grinyuk309 написав:

в мене немає ніяких критеріїв для сортування

"Впорядкований" і "відсортований" - це, фактично, синоніми, перше слово каже про стан масиву, а друге - що над масивом здійснено процедуру, якою приводять до цього стану. Якщо у вас є критерії упорядкування для M3, то вони ж мають застосовуватися для сортування M1 і M2.

Подякували: leofun011

14

Re: Злиття масивів

grinyuk309 написав:

в мене немає ніяких критеріїв для сортування

Критерій вам мав би надати той, для кого ви пишете програму (замовник або викладач). Зверніться до нього з цим питанням.

Подякували: koala1

15

Re: Злиття масивів

В мізерній інструкції до лабораторної я вичитав таке
Упорядкування масиву – це зміна порядку розташування його елементів за певним критерієм. Наприклад, в числовому масиві це може бути упорядкування елементів за зростанням значень або за їх спаданням
Зачить критеріїв є тільки два зростання і спадання, тому я написав програму, яка об'єднює два масиви в третій і упорядкоовує чи сортує за цими критеріями

#include "pch.h"
#include <iostream>
#define N 10

int main()
{
    
    setlocale(LC_CTYPE, "ukr");
    int n, m, i, j;
    float m1[N], m2[N], m3[N], t;
    printf("enter size m1=");
    scanf_s("%i", &n);
    printf("enter size m2=");
    scanf_s("%i", &m);
    for (i = 0;i < n;i++) //заповнюю перший масив
    {
        printf("m1[%i]=", i);
        scanf_s("%f", &m1[i]);
    }
    for (i = 0;i < m;i++) //заповнюю другий масив
    {
        printf("m2[%i]=", i);
        scanf_s("%f", &m2[i]);
    }
    for (i = 0;i < n;i++) //заповню третій масив елементами першого
    {
        m3[i] = m1[i];  
    }
    for (j = n, i = 0;i < m;i++,j++) // дозаповнюю третій масив елементами другого
    {
        m3[j] = m2[i];
    }
    printf("\nЗлитий масив\n"); 
    for (i = 0;i < n + m;i++) //виводжу результат заповнень
    {
        printf("m3[%i]=%5.1f\t", i, m3[i]);
    }
    for (i = 0;i < n + m - 1;i++)        //сортуєм за спаданням
    {
        for (j = i + 1;j < n + m;j++)
        {
            if (m3[j] > m3[i])
            {
                t = m3[i];
                m3[i] = m3[j];
                m3[j] = t;
            }
        }
    }
    printf("\n\nМасив вiдсортований за спаданням\n");
    for (i = 0;i < n + m;i++)
    {
        printf("m3[%i]=%5.1f\t", i, m3[i]);
    }
    printf("\n\n");
    for (i = 0;i < n + m - 1;i++)        //сортуєм за зростанням
    {
        for (j = i + 1;j < n + m;j++)
        {
            if (m3[j] < m3[i])
            {
                t = m3[i];
                m3[i] = m3[j];
                m3[j] = t;
            }
        }
    }
    printf("Масив вiдсортований за зростанням\n");
    for (i = 0;i < n + m;i++)
    {
        printf("m3[%i]=%5.1f\t", i, m3[i]);
    }
    printf("\n\n");
    return 0;
}

Результат:
enter size m1=2
enter size m2=3
m1[0]=1.1
m1[1]=2.1
m2[0]=3.1
m2[1]=4.1
m2[2]=5.1

Злитий масив
m3[0]=  1.1     m3[1]=  2.1     m3[2]=  3.1     m3[3]=  4.1     m3[4]=  5.1

Масив вiдсортований за спаданням
m3[0]=  5.1     m3[1]=  4.1     m3[2]=  3.1     m3[3]=  2.1     m3[4]=  1.1

Масив вiдсортований за зростанням
m3[0]=  1.1     m3[1]=  2.1     m3[2]=  3.1     m3[3]=  4.1     m3[4]=  5.1

16

Re: Злиття масивів

А тепер дивіться, в чому мала бути ідея. Час сортування, тим більше бульбашкою - O(n^2). Тобто час на сортування 200 елементів буде більшим за час сортування 100 елементів не в 2, а в 4 рази. А час на злиття двох упорядкованих масивів у один - лінійний, O(m+n), де m, n - розміри цих масивів. Дивіться, як:
1. Якщо в масивах ще є елементи, то порівнюємо перші елементи обох масивів.
1.1. Менший переписуємо в результат і зсуваємося в тому масиві на 1.
2. Якщо елементи в одному скінчилися, переписуємо другий масив в кінець результату.
Десь так:

int size_a=10, size_b=20;
int a[size_a],b[size_b],c[size_a+size_b];//вважаємо, що A,B - впорядковані
int idx_a=0,idx_b=0,idx_c=0;//індекси
while(idx_a<size_a && idx_b<size_b)
{
  if(a[idx_a]<=b[idx_b]){
    c[idx_c++] = a[idx_a++];
  } else {
    c[idx_c++] = b[idx_b++];
  }
}
while(idx_a<size_a) {//якщо ми вийшли з циклу, то якийсь з індексів уже за межами, і решту треба просто переписати
    c[idx_c++] = a[idx_a++];
}
while(idx_b<size_b) {
    c[idx_c++] = b[idx_b++];
}
Подякували: ping, leofun012

17

Re: Злиття масивів

А тепер дивіться, в чому мала бути ідея.

а можна кожен з цих двох розбити на ще два і ще скороти ти час?

18

Re: Злиття масивів

ping написав:

А тепер дивіться, в чому мала бути ідея.

а можна кожен з цих двох розбити на ще два і ще скороти ти час?

Так вони ж уже сортовані мають бути.

Подякували: leofun011

19

Re: Злиття масивів

koala написав:
ping написав:

А тепер дивіться, в чому мала бути ідея.

а можна кожен з цих двох розбити на ще два і ще скороти ти час?

Так вони ж уже сортовані мають бути.

у Вас є інсайт щодо того, яка має бути умова? Це щось з якогось посібника чи навчального курсу?
бо

Дано два довільні одновимірні масиви дійсних чисел М1 і М2.

тут про це не сказано нічого.

Подякували: leofun011

20

Re: Злиття масивів

ping написав:

у Вас є інсайт щодо того, яка має бути умова? Це щось з якогось посібника чи навчального курсу?
бо

Дано два довільні одновимірні масиви дійсних чисел М1 і М2.

тут про це не сказано нічого.

Бо я пояснював алгоритм сортування злиттям, а не розв'язок цієї задачі.

Подякували: ping, leofun012