Найти ошибку в алгоритме сортировки?

Question

[Stadinov Denis]

Всем привет! Подскажите где я не прав.
Я решил отсортировать массив по возрастанию. Без использования функции.

$a = array(2,7,200,6);
$b = $a;

for($i=0; $i < count($a); ++$i)
{
    $save_j = $i;

    for($j = $i; $j < count($a); ++$j)
    {
        if ($a[$i] < $a[$j])
        {
            $a[$i] = $a[$j];
            $save_j = $j;
        }
    }

    $a[$save_j] = $b[$i];

}

Но на выходе получаю

array (size=4)
0 => int 200
1 => int 7
2 => int 6
3 => int 6

А этот вариант верный

$a = array(2,200,7,300,4,44,5,102);

for($i=0; $i < count($a); ++$i)
{
    $save_j = $i;
    $save_max = $a[$i];

    for($j = $i; $j < count($a); ++$j)
    {
        if ($save_max < $a[$j])
        {
            $save_max = $a[$j];
            $save_j = $j;
        }
    }

    $a[$save_j] = $a[$i];
    $a[$i] = $save_max;
}

array (size=8)
0 => int 300
1 => int 200
2 => int 102
3 => int 44
4 => int 7
5 => int 5
6 => int 4
7 => int 2

По мне они одинаковые, да и логика вроде верная.
Но где-то я ошибся, а где понять не могу.

Answer 1

[Rsa97]

Странно, а в каком месте стоял var_dump? Вообще-то, в конце работы вашего алгоритма получаем

array(4) { [0]=> int(200) [1]=> int(7) [2]=> int(6) [3]=> int(6) }

То есть сортировка работает, только по убыванию.

Comments

[Stadinov Denis]

С результатом ты прав, я не тот var_dump() вставил, но сейчас подправил (спасибо).
А вот в сортировке пропало значение «2»

[Rsa97]

Угу. Смотрим по шагам. Ставим var_dump после $a[$save_j] = $b[$i];:

array(4) { [0]=>int(200) [1]=>int(7) [2]=>int(2) [3]=>int(6) }
array(4) { [0]=>int(200) [1]=>int(7) [2]=>int(2) [3]=>int(6) }
array(4) { [0]=>int(200) [1]=>int(7) [2]=>int(6) [3]=>int(200) }

Стоп! На третьем шаге ошибка. Причина - массив $b ничего не знает от том, что к этому шагу в третьем элементе $a уже находится не 200, а 2. Решение - заменить $a[$save_j] = $b[$i]; на $b[$save_j] = $a[$save_j] = $b[i];.

[Stadinov Denis]

@Rsa97: спасибо! только я что-т не понимаю почему это работает (:
Но если, что сам буду искать ответ!

Answer 2

[ugodrus]

Страшная у вас конструкция. Особенно в циклах count(). sizeof() работает быстрее. Да и в циклы не стоит вставлять подобное т.к. эти вычисления происходят при каждой итерации цикла. И ещё... Есть масса отличных алгоритмов сортировки. Например методом Шелла.

function ShellSort($elements,$length) {
     $k=0;
     $gap[0] = (int) ($length / 2);
 
     while($gap[$k] > 1) {
         $k++;
         $gap[$k]= (int)($gap[$k-1] / 2);
     }//end while
 
     for($i = 0; $i <= $k; $i++){
         $step=$gap[$i];
 
         for($j = $step; $j < $length; $j++) {
             $temp = $elements[$j];
             $p = $j - $step;
             while($p >= 0 && $temp < $elements[$p]) {
                 $elements[$p + $step] = $elements[$p];
                 $p= $p - $step;
             }//end while
             $elements[$p + $step] = $temp;
         }//endfor j
     }//endfor i
 
     return $elements;
 }

Метод сортирует массив максимум в 1.65 прохода (в зависимости от длины массива). В вашем случае количество манипуляций - длина массива в квадрате. Попытка зачтена, метод - мягко говоря не очень.

Comments

[Stadinov Denis]

Спасибо, очень ценные советы (за реализацию алгоритма на php отдельный респект).

[ugodrus]

Спасибо скажешь Google когда поищешь алгоритмы сортировки.

[ugodrus]

А метод просто превосходный. Я его в свое время расширял и сортировал с помощью него двухмерные массивы по определённым полям.

Answer 3

[Jaty4]

if ($save_max > $a[$j])
у вас ашибка в сравнении

Comments

[Stadinov Denis]

фтарой вариант работает идиально