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

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

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

Пусть есть два массива a и b, размерами m и n соответственно. Массивы отсортированы по возрастанию. Необходимо слить массивы в один массив c размером (m + n). Определим для массивов новый тип T и макрос CMP_LT, необходимый для сравнения элементов.

Будем проходить по обоим массивам, сравнивая элементы, и копировать в выходной массив меньший их них. После этого окажется, что какой-то из массивов скопирован не до конца. В цикле скопируем оставшиеся элементы.

typedef int T;

#define CMP_LT(a, b) ((a) < (b))

void merge(const T *a, const T *b, size_t n, size_t m, T *c) {
        size_t i, j, k;
        i = j = k = 0;
        //Копируем в массив c меньшее значение,
        //увеличивая при этом счётчики i, j, k
        while (i < n && j < m) {
                if (CMP_LT(a[i], b[j])) {
                        c[k++] = a[i++];                
                } else {
                        c[k++] = b[j++];
                }
        }
        //Если какой-то массив прошли не до конца,
        //то копируем оставшиеся элементы
        while (i < n) {
                c[k++] = a[i++];
        }
        while (j < m) {
                c[k++] = b[j++];
        }
}

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

Галопирующий режим

Пусть имеется два массива a и b следующего вида

T a[] = {1, 2, 3, 3, …, 1000};
T b[] = {2001, 2002, 2003, …, 10000};

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

Таким образом, если элемент a[i] меньше b[j], то зафиксируем j и начальное значение i (i == old_i) и будем проверять элементы из массива a до тех пор, пока a[i] < b[j]. Затем скопируем участок от i_old до i.

Такой способ слияния обычно включается в том случае, если по прошествии N копирований элемент a[i] ещё остаётся меньше b[j]. Переход к просмотру элементов без копирования называется переходом в галопирующий режим. N обычно ставят равным семи.

void gmerge(const T *a, const T *b, size_t n, size_t m, T *c) {
        size_t i, old_i, j, old_j, k;
        i = j = k = old_i = old_j = 0;
        while (i < n && j < m) {
                if (CMP_LT(a[i], b[j])) {
                        i++;
                        while (CMP_LT(a[i], b[j]) && i < n) {
                                i++;
                        }
                        memcpy(&c[k], &a[old_i], (i - old_i)*sizeof(T));
                        k += (i - old_i);
                        old_i = i;
                } else {
                        j++;
                        while (CMP_LT(b[j], a[i]) && j < m) {
                                j++;
                        }
                        memcpy( &c[k], &b[old_j], (j - old_j)*sizeof(T));
                        k += (j - old_j);
                        old_j = j;
                }
        }
        if (i < n) {
                memcpy(&c[k], &a[i], (n - i)*sizeof(T));
        }
        if (j < n) {
                memcpy(&c[k], &b[j], (m - j)*sizeof(T));
        }
}

Вот пример с переходом в галопирующий режим после достижения значения GM_TRESHOLD равного, в данном случае, трём. Переменная from_a определяет, из какого массива было проведено копирование в прошлый раз.

#define GM_THRESHOLD 3

void gmergei(const T *a, const T *b, size_t n, size_t m, T *c) {
        size_t i, old_i, j, old_j, k, gmcnt;
        int from_a = 0;
        i = j = k = gmcnt = 0;
NORMAL_MODE:
        while (i < n && j < m) {
                if (CMP_LT(a[i], b[j])) {
                        c[k++] = a[i++];
                        if (from_a) {
                                gmcnt++;
                        } else {
                                from_a = 1;
                                gmcnt = 0;
                        }
                }
                else {
                        c[k++] = b[j++];
                        if (from_a) {
                                from_a = 0;
                                gmcnt = 0;
                        }
                        else {
                                gmcnt++;
                        }
                }
                if (gmcnt >= GM_THRESHOLD) {
                        goto GALOPING_MODE;
                }
        }
        goto ENDING;
GALOPING_MODE:
        old_i = i;
        old_j = j;
        while (i < n && j < m) {
                if (CMP_LT(a[i], b[j])) {
                        i++;
                        while (CMP_LT(a[i], b[j]) && i < n) {
                                i++;
                        }
                        memcpy(&c[k], &a[old_i], (i - old_i)*sizeof(T));
                        k += (i - old_i);
                        old_i = i;                      
                }
                else {
                        j++;
                        while (CMP_LT(b[j], a[i]) && j < m) {
                                j++;
                        }
                        memcpy(&c[k], &b[old_j], (j - old_j)*sizeof(T));
                        k += (j - old_j);
                        old_j = j;
                }
                gmcnt = 0;
                goto NORMAL_MODE;
        }
ENDING:
        if (i < n) {
                memcpy(&c[k], &a[i], (n - i)*sizeof(T));
        }
        if (j < n) {
                memcpy(&c[k], &b[j], (m - j)*sizeof(T));
        }
}

Поиск вперёд можно существенно ускорить, каждый раз прибавляя к переменной-итератору не единицу, а значения, растущие как ряд Фибоначчи. Но это уже другая тема.

Оглавление