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

Теги: Слияние массивов, галопирующий режим



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

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

Пусть есть два массива 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));
	}
}

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

Q&A

Всё ещё не понятно? – пиши вопросы на ящик email
Оглавление