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