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

@Fortra · Регистрация: 14.12.2014

Студворк — интернет-сервис помощи студентам

выполнить слияние упорядоченного по возрастанию А(m) и неупорядоченного(n) массивов(n<<m) в упорядоченный по не убыванию массив С.

@hoggy · 16.12.2014, 02:49

http://rextester.com/SZKW83882

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
#include <set>
#include <iostream>
 
 
template<size_t N, size_t M>
int (&merge(  const int (&a)[N], const int (&b)[M] )   )[N+M]
{
    ::std::multiset<int> s(a, a+N);
    s.insert(b, b+M);
    
    static int c[N+M];
    
    size_t n=0;
    for(const auto& e: s)
        c[n] = e,
        ++n;
   
    return c;
}
    
 
template<size_t N> 
::std::ostream& operator<< (::std::ostream& ss, const int (&ar)[N] )
{
    for(const auto& e: ar)
        ss<< e <<", ";
    return ss;
}
    
int main()
{
    std::cout << "Hello, world!\n";
    
    const int a[]= {1,2,3,4,5};
    const int b[]= {5,2,7,9};
    
    ::std::cout<< "array a: { "<< a <<"};\n";
    ::std::cout<< "array b: { "<< b <<"};\n";
    
    const auto& r = merge(a,b);
    
    ::std::cout<< "result : { "<< r <<"};\n";
}

@Fortra · 16.12.2014, 13:58 **[ТС]**

выполнить слияние упорядоченного по возрастанию А(m) и неупорядоченного(n) массивов(n<<m) в упорядоченный по не убыванию массив С.(НЕ ипользовать функции).

MrGluck · 16.12.2014, 14:28

Сообщение от Fortra

НЕ ипользовать функции

А main можно?

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

@Fortra · 16.12.2014, 14:29 **[ТС]**

да можна)

@tyreu · 16.12.2014, 15:16

а что за template?

MrGluck · 16.12.2014, 15:42

Сообщение от tyreu

а что за template?

Ключевое слово. Здесь используется для того, чтобы можно было передавать массив в функцию, не указывая размер.

@tyreu · 16.12.2014, 15:44

Интересно, спасибо

@Fortra · 16.12.2014, 23:19 **[ТС]**

а как понять
for(const auto& e: ar)
ss<< e <<", ";

@hoggy · 17.12.2014, 20:46

Сообщение от Fortra

НЕ ипользовать функции).

http://rextester.com/WOL1751

Кликните здесь для просмотра всего текста

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
#include <set>
#include <iostream>
 
int main()
{
    ::std::cout << "Hello, world!\n";
    
    const int a[]= {1,2,3,4,5};
    ::std::cout<< "array a: { ";
    for(const auto& e: a)
        ::std::cout<< e <<", ";
    ::std::cout << "};\n";
    
 
    const int b[]= {5,2,7,9};    
    ::std::cout<< "array b: { ";
    for(const auto& e: b)
        ::std::cout<< e <<", ";
    ::std::cout << "};\n";
 
    enum { A = sizeof(a)/sizeof(a[0]) };
    enum { B = sizeof(b)/sizeof(b[0]) };
    enum { C = A + B };
    int c[C];
    
    
    ::std::multiset<int> s(a, a+A);
    s.insert(b, b+B);
    
    size_t n=0;
    for(const auto& e: s)
        c[n] = e,
        ++n;
    
    
    ::std::cout<< "result : { ";
    for(const auto& e: c)
        ::std::cout<< e <<", ";
    ::std::cout << "};\n";
    
}

Добавлено через 2 минуты

Сообщение от Fortra

а как понять
for(const auto& e: ar)
ss<< e <<", ";

Цикл по всей коллекции (в данном случае по всему массиву)

Здесь ar - массив, по которому нужно пробежаться
e - элемент массива, который вытаскивается из массива на каждом шаге цикла

а это инструкция, которую нужно выполнить над каждым элементом e

C++
1
ss<< e <<", ";

MrGluck · 18.12.2014, 19:18

Есть for цикл по коллекции, но почему-то по прежнему идёт вычисление количества элементов через деление размеров. Есть же std::begin + std::end. На статических массивах работает замечательно.

C++
1
std::multiset<int> s(std::begin(a), std::end(a));

@hoggy · 18.12.2014, 20:23

Сообщение от MrGluck

Есть же std::begin + std::end. На статических массивах работает замечательно.

Это - не принципиально.

Принципиально получить массив-результат-слияния.

C++
1
2
enum { C = A + B };
int c[C];

Что бы определить его размер, необходимо определить размеры исходных массивов.

MrGluck · 18.12.2014, 20:40

Сообщение от hoggy

Что бы определить его размер, необходимо определить размеры исходных массивов.

Или же использовать

C++
1
s.size()

(хоть это и бессмысленно)

@hoggy · 18.12.2014, 21:51

Сообщение от MrGluck

Или же использовать

на с++ размер массива должен быть известен времени компиляции.

MrGluck · 18.12.2014, 22:47

Сообщение от hoggy

на с++ размер массива должен быть известен времени компиляции.

Да что вы говорите

C++
1
int *c = new int[s.size()];

@hoggy · 18.12.2014, 23:26

Сообщение от MrGluck

Да что вы говорите
int *c = new int[s.size()];

Здесь нет массива.

MrGluck · 19.12.2014, 10:48

Сообщение от hoggy

Здесь нет массива.

Динамические массивы

В стандарте например это массивами называют.

5.3.4 New
8. <...> If the allocated type is an array type, the allocation
function’s name is operator new[] and the deallocation function’s name is operator delete[]. <...>

Ilot · 19.12.2014, 11:04

MrGluck, эм... а почему нет?:

C++
1
2
3
4
5
int a[M]; //<-sort
int b[N]; //<-unsort
int c[M + N];//<-out
std::sort(b, b + N);
std::merge(a, a + M, b, b + N, c) ;

MrGluck · 19.12.2014, 11:09

Сообщение от Ilot

MrGluck, эм... а почему нет?:

Не по теме:

Я хотел понять по какому алгоритму он предполагал сии действия, выразился некорректно (двусмысленно)

@hoggy · 19.12.2014, 12:58

Сообщение от MrGluck

В стандарте например это массивами называют.

выделение памяти под массив. Самого массива при этом нет. Есть операция выделения и указатель.

Добавлено через 3 минуты

Сообщение от Ilot

эм... а почему нет?:
int a[M]; //<-sort
int b[N]; //<-unsort
int c[M + N];//<-out
std::sort(b, b + N);
std::merge(a, a + M, b, b + N, c)

Потому что нужно сначала сделать слияние, и только потом сортировать.

Новые блоги и статьи Все статьи Все блоги /
Символьное дифференцирование igorrr37 13.02.2026 / * Логарифм записывается как: (x-2)log(x^2+2) - означает логарифм (x^2+2) по основанию (x-2). Унарный минус обозначается как ! в-строка - входное арифметическое выражение в инфиксной(обычной). . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .

@Fortra 0 / 0 / 0 Регистрация: 14.12.2014 Сообщений: 10

	Слияние массивов в упорядоченный массив 16.12.2014, 01:40. Показов 2432. Ответов 31 Метки нет (Все метки) выполнить слияние упорядоченного по возрастанию А(m) и неупорядоченного(n) массивов(n<<m) в упорядоченный по не убыванию массив С. 0

@Fortra 0 / 0 / 0 Регистрация: 14.12.2014 Сообщений: 10
	16.12.2014, 13:58 [ТС]
	выполнить слияние упорядоченного по возрастанию А(m) и неупорядоченного(n) массивов(n<<m) в упорядоченный по не убыванию массив С.(НЕ ипользовать функции). 0

@Fortra 0 / 0 / 0 Регистрация: 14.12.2014 Сообщений: 10
	16.12.2014, 14:29 [ТС]
	да можна) 0

@tyreu Заблокирован
	16.12.2014, 15:16
	а что за template? 0

@tyreu Заблокирован
	16.12.2014, 15:44
	Интересно, спасибо 0

@Fortra 0 / 0 / 0 Регистрация: 14.12.2014 Сообщений: 10
	16.12.2014, 23:19 [ТС]
	а как понять for(const auto& e: ar) ss<< e <<", "; 0