21

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

koala написав:

А тепер дивіться, в чому мала бути ідея. Час сортування, тим більше бульбашкою - 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++];
}

Складно зрозуміти, мені можна спробувати підставити свої дані в цей фрагмент коду?

22 Востаннє редагувалося ReAl (07.12.2019 23:03:53)

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

ping написав:

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

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

Не лише можна, а треба — якщо робити «сортування зливанням», яке має складність O(n lg n) (див. CLRS розділ 2).

Але таке враження, що в умові «Дано два довільні одновимірні масиви дійсних чисел М1 і М2. Сформувати злиттям цих масивів упорядкований масив М3.» мали на увазі лише операцію зливання як елемент такого сортування розділенням масиву на шматки донизу, а потім піднімання-зливання для отримання сортування («розділяй і володарюй», див там само). Бо в умові нема нічого про ділення далі (хоча й нема нічого щодо їхньої упорядкованості, але це легше забути, ніж забути написати, що треба ділити далі). І те буде на наступному уроці ;)

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