Слияние отсортированных массивов
Слияние отсортированных массивов
Алгоритм слияния отсортированных массивов в один отсортированный массив является одним из самых простых алгоритмов. Он используется в качестве вспомогательного инструмента в других алгоритмах (например, сортировке слиянием).
Пусть есть два массива 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));
}
}
Поиск вперёд можно существенно ускорить, каждый раз прибавляя к переменной-итератору не единицу, а значения, растущие как ряд Фибоначчи. Но это уже другая тема.
