В настоящее время я изучаю алгоритмы сортировки и нашел сортировку слиянием. Я почти ничего не смог найти для него, кроме нескольких статей и ссылок на книги. Итак, этот алгоритм был открыт Лестером Фордом-младшим и Селмером Джонсоном. Частично это описано здесь: http://www2.warwick.ac.uk/fac/sci/dcs/teaching/material/cs341/FJ.pdf
Моя проблема сейчас заключается в том, чтобы понять, как работает часть вставки, и, кроме того, какая последовательность чисел 1, 3, 5, 11, упомянутая в объяснении, как вставить. Это выглядит так знакомо, но я просто не могу вспомнить, что это было.
То, что у меня есть на данный момент, выглядит так:
//pointer to array, array size, element size, compare function pointer
void sort(void *data, size_t n, size_t s, int (*fcomp)(void*, void*))
{
if(!data) return;
if(n < 2 || s == 0) return;
size_t i = 0, j = 0, k = 0, l = 0, r = 0, m = 0;
void *be = malloc((n/2)*s); //elements greater in pair comparison
void *le = malloc((n/2 + n%2)*s);//elements lesser in pair comparison
void *mc = malloc(n*s); //main chain
//compare pair-wise K_1:K_2, ... , K_N:K_N-1
for(i = 0; i < n; i+=2)
{
if(fcomp(voidAdd(data, s, i), voidAdd(data, s, i+1)) >= 0)
{
//element at i bigger than i+1 so, put it in be and i+1 in le
memcpy(voidAdd(be, s, k++), voidAdd(data, s, i), s);
memcpy(voidAdd(le, s, j++), voidAdd(data, s, i+1), s);
}
else
{
//element i+1 bigger than i so put it in be and i in le
memcpy(voidAdd(be, s, k++), voidAdd(data, s, i+1), s);
memcpy(voidAdd(le, s, j++), voidAdd(data, s, i), s);
}
}
sort(be, n/2, s, fcomp); //recursivly repeat process for bigger elements
/*
now we have chain a_1, ..., a_n/2 and b_1, ..., b_n/2 with a_i > b_i and
a_1 < ... a_n/2
*/
memcpy(mc, le, s); //insert b_1 into the main-chain
memcpy(voidAdd(mc, s, 1), be, (n/2)*s); //copy a_1, ... a_n/2 in main chain
//now we have b_1, a_1, ..., a_n/2 as main chain
//start insertion here
j = n/2 + 1;
for(i = 1; i < n/2; i++)
{
k = ...;//number from sequence 1, 3, 5, 11, ...
}
memcpy(data, mc, n*s);
free(mc);
free(be);
free(le);
}
Из того, что написано в связанном pdf, в него нужно вставить b_3, b_2, b_5, b_4... в основную цепочку теперь с бинарной вставкой, но я не уверен, как именно это сделать и откуда они берут эти числа .
t(k) = (2^(k+1) + (-1)^k)/3, где^— оператор степени. - person orlp schedule 03.01.2015