Увлекся я недавно изучением работы классических алгоритмов сортировки. Большинстов, конечно из них нетривиальны, но ... платить за эффект нужно)...
На сколько я понял из прочитанного мною - 2 самых популярных это "слиянием"(на сколько знаю - он реализован во фреймворке джавы, это точно), ну и естественно, "быстрая сортировка", которая в качестве реализации в пхп для sort() и прочих была задействована.
А волнует в даной теме меня вот что... Я хотел на пхп протрассировать алгоритм слиянием, и... немогу корректно выполнить его... Я уже записал его вплоть до самых мелочей согласно псевдокоду, написанном в книге (Кормен и компания - "Алгоритмы. Построение и анализ"), да я вообще пробовал его реализовать по другому, но все безуспешно...
В чем проблема?
Сначала предоставлю сам код, а потом, как обычно постараюсь описать...
$input_arr =
array(4,
1,
3,
8,
7,
5,
2,
9,
6);
function mergeSort
($ar,
$first,
$last)
{
if($first <
$last)
{
$middle =
floor( ($first+
$last) /
2 );
echo "first: ".
$first.
"; last: ".
$last.
"; middle: ".
$middle.
"<br />";
mergeSort
($ar,
$first,
$middle);
echo 'trying invoke mergeSort() for second part...<br />';
mergeSort
($ar,
$middle+1,
$last);
echo 'trying invoke merge()...<br />';
merge
($ar,
$first,
$middle,
$middle+1,
$last);
}
}
function merge
($ar,
$first1,
$last1,
$first2,
$last2)
{
$finalStart =
$first1;
$finalEnd =
$last2;
echo 'merge invoked...<br />';
$c =
0;
$temp =
array();
while($start1 <=
$last1 &&
$start2 <=
$last2)
{
if($ar[$start1] <
$ar[$start2])
{
$temp[$c] =
$ar[$start1];
$start1++;
}
else
{
$temp[$c] =
$ar[$start2];
$start2++;
}
$c++;
}
if($start1 <=
$last1)
{
for($i =
$start1;
$i <
$last1;
$i++
)
{
$temp[$c] =
$ar[$i];
}
}
else
{
for($i =
$start2;
$i <
$last2;
$i++
)
{
$temp[$c] =
$ar[$i];
}
}
$c =
0;
for($i =
$finalStart;
$i<
$finalEnd;
$i++
)
{
$ar[$i] =
$temp[$c];
$c++;
}
}
mergeSort
($input_arr,
0,
count($input_arr));
Результаты выполнения:
first: 0; last: 9; middle: 4
first: 0; last: 4; middle: 2
trying invoke mergeSort() for second part...
first: 3; last: 4; middle: 3
first: 3; last: 3; middle: 3
first: 3; last: 3; middle: 3
first: 3; last: 3; middle: 3
first: 3; last: 3; middle: 3
first: 3; last: 3; middle: 3
first: 3; last: 3; middle: 3
first: 3; last: 3; middle: 3
first: 3; last: 3; middle: 3
first: 3; last: 3; middle: 3
Вообщем, то что зацикливание по рекурсии, это понятно(хотя и не должно)... Это пол беды.
Но меня интересует не то.
ПОЧЕМУ сначала впритык пополам делится первая часть массива (соответственно на этом основании для второй части и выходят неправильные данные)... И вообще, в следствии функция merge() даже не вызывается?
Насколько я понимаю, согласно теории(
http://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D1%81%D0%BB%D0%B8%D1%8F%D0%BD%D0%B8%D0%B5%D0%BC)
все должно проходить по очереди. Тоесть сначала мы выбираем одним рекурсивным вызовом mergeSort() первую половину, а следующим - вторую, и только потом должна на этих основаниях вызыватся merge() чтобы посоиденять в отсортированном порядке две части.
Я пробовал реализовать по тому примеру что и на википедии(где пример на паскале), где рекурсивные вызовы присваиваются определенным переменным, но увы, результаты - те же(.
Почему рекурсия ведет себя таким образом? что я делаю неправильно?
p.s. Пожалуйста, не пишите чтото вроде "юзай sort() и парся с чем не надо". Просто исследую в учебных целях и ту теорию знать любому програмисту надо...
