ФорумПрограммированиеPHP для идиотов → Попытка реализации алгоритма сортировки слиянием на пхп.

Попытка реализации алгоритма сортировки слиянием на пхп.

  • Rotten

    Сообщения: 2243 Репутация: N Группа: Адекваты

    Spritz 9 марта 2010 г. 4:58

    Увлекся я недавно изучением работы классических алгоритмов сортировки. Большинстов, конечно из них нетривиальны, но … платить за эффект нужно)…
    На сколько я понял из прочитанного мною - 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() и парся с чем не надо". Просто исследую в учебных целях и ту теорию знать любому програмисту надо…
  • Nyaah

    Сообщения: 574 Репутация: N Группа: Джедаи

    Spritz 9 марта 2010 г. 5:37, спустя 39 минут 52 секунды

    а) следи за размерами массива (у тебя mergeSort($ar, $first, $last), $last - индекс последнего элемента, а ты передаёшь count($input_arr)? размер на самом деле = $last + 1)
    б) следи за размерами массива =) (merge($ar,$first,$middle,$middle+1,$last); - $middle может оказаться раыным $last, а ты передаёшь $middle+1)
    в) слияние криво написано, как минимум ты в названиях переменных запутался ($start1 и $start2 не определены, юзай E_ALL error reporting)
    г) у тебя ничего не отсортируется, так как Карман писал в расчёте на то, что массивы передаются по указателю, а не копируются, поэтому у него функии, принимающие строки/массивы/матрицы и вообще все что сложнее инта не возвращают ничего кроме була/инта, посему тебе надо передавать массив по ссылке, те mergeSort(&$ar, $first, $last);

    А вообще да, хорошее начинание, только запнулся ты чего-то рановато, буквально на вервых страницах =)
    Work, buy, consume, die
  • Rotten

    Сообщения: 2243 Репутация: N Группа: Адекваты

    Spritz 9 марта 2010 г. 5:55, спустя 17 минут 48 секунд

    Naaayh, Да согласен…. ошибок насобирается пожалуй. Я просто этот алгоритм 7й раз гдето переписываю)….
    я пробовал по разному передавать размеры. И так чтобы last был именно last а не размером массива, тоже.
    mergeSort($input_arr,0,(count($input_arr) - 1));

    И со ссилками чтобы явно массивы передавались - тоже. Вот, сейчас изменил….
    результаты, увы, те же(…
    Спустя 267 сек.
    Хм… повела себя программа немного по-другому, когда изменил количество элементов на 8.
    Мда, гемороя тут хватает… буду дальше штудировать)…
  • Rotten

    Сообщения: 2243 Репутация: N Группа: Адекваты

    Spritz 9 марта 2010 г. 6:20, спустя 25 минут 6 секунд

    Вот переписан.
    function mergeSort(&$ar, $first, $last)
    {
    if($first < $last /*floor( ($first+$last) / 2 ) > 1*/)
    {
    $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($first1 <= $last1 && $first2 <= $last2)
    { echo "first1: ".$first1."; first2: ".$first2."<br />";
    if($ar[$first1] < $ar[$first2])
    {
    $temp[$c] = $ar[$first1];
    $first1++;
    }
    else
    {
    $temp[$c] = $ar[$first2];
    $first2++;
    }
    $c++;
    }

    if($first1 <= $last1)
    {
    for($i = $first1; $i < $last1; $i++)
    {
    $temp[$c] = $ar[$i];
    }
    }
    else
    {
    for($i = $first2; $i < $last2; $i++)
    {
    $temp[$c] = $ar[$i];
    }
    }

    $c = 0;

    for($i = $finalStart; $i< $finalEnd; $i++)
    {
    $ar[$i] = $temp[$c];
    $c++;
    }

    echo "<pre>";
    print_r($ar);
    echo "</pre>";
    }



    mergeSort($input_arr,0,(count($input_arr) - 1));


    Результаты:
    Array
    (
    [0] => 4
    [1] => 1
    [2] => 3
    [3] => 8
    [4] => 7
    [5] => 5
    [6] => 2
    [7] => 9
    [8] => 6
    )
    first: 0; last: 8; middle: 4
    first: 0; last: 4; middle: 2
    first: 0; last: 2; middle: 1
    first: 0; last: 1; middle: 0
    trying invoke mergeSort() for second part…
    trying invoke merge()…
    merge invoked…
    first1: 0; first2: 1
    Array
    (
    [0] => 1
    [1] => 1
    [2] => 3
    [3] => 8
    [4] => 7
    [5] => 5
    [6] => 2
    [7] => 9
    [8] => 6
    )
    trying invoke mergeSort() for second part…
    trying invoke merge()…
    merge invoked…
    first1: 0; first2: 2
    first1: 1; first2: 2

    ……….


    Вооьщем, видно, что рекурсия так и дальше замыкается с первого вызова сама в себя. И merge() при этом не вызывается…
    first: 0; last: 8; middle: 4
    first: 0; last: 4; middle: 2
    first: 0; last: 2; middle: 1
    first: 0; last: 1; middle: 0

  • Nyaah

    Сообщения: 574 Репутация: N Группа: Джедаи

    Spritz 9 марта 2010 г. 7:43, спустя 1 час 23 минуты 3 секунды

    // $middle = floor( ($first+$last) / 2 );
    $middle = $first + floor( ($first+$last) / 2 ); // и на твоей улице будет праздник =)
    Спустя 210 сек.
    суть в том, что ты указываешь не середину отрезка [$first; $last], а половуниу расстояния между ними
    Work, buy, consume, die

Пожалуйста, авторизуйтесь, чтобы написать комментарий!