Improved Shell Sort

shell.php

<?

function shell_sort($a){
        $step   = count($a) - 1;

        while ( true ){
                $sorted = false;


                echo sprintf("Step %3d\n", $step);


                while ( ! $sorted ){
                        $sorted = true;


                        for ($i = 0; $i < count($a); $i++)
                                echo sprintf("[ %4d ] ", $a[$i]);
                        echo "\n";


                        for ($i = 0; $i < count($a) - $step; $i++){
                                $j = $i + $step;

                                if ($a[$i] > $a[$j]){
                                        $tmp   = $a[$i];
                                        $a[$i] = $a[$j];
                                        $a[$j] = $tmp;

                                        $sorted = false;
                                }
                        }
                }



                if ($sorted && $step == 1)
                        break;

                $step = (int) ($step / 2 + 0.5);
        //      $step = (int) ($step / 2);
                if ($step < 1)
                        $step = 1;
        }

        return $a;
}



$a = array(324,23,2,35,6,333,224,6555,23,2,4,78);

print_r(shell_sort($a));

Step 11
[ 324 ] [ 23 ] [ 2 ] [ 35 ] [ 6 ] [ 333 ] [ 224 ] [ 6555 ] [ 23 ] [ 2 ] [ 4 ] [ 78 ]
[ 78 ] [ 23 ] [ 2 ] [ 35 ] [ 6 ] [ 333 ] [ 224 ] [ 6555 ] [ 23 ] [ 2 ] [ 4 ] [ 324 ]
Step 6
[ 78 ] [ 23 ] [ 2 ] [ 35 ] [ 6 ] [ 333 ] [ 224 ] [ 6555 ] [ 23 ] [ 2 ] [ 4 ] [ 324 ]
[ 78 ] [ 23 ] [ 2 ] [ 2 ] [ 4 ] [ 324 ] [ 224 ] [ 6555 ] [ 23 ] [ 35 ] [ 6 ] [ 333 ]
Step 3
[ 78 ] [ 23 ] [ 2 ] [ 2 ] [ 4 ] [ 324 ] [ 224 ] [ 6555 ] [ 23 ] [ 35 ] [ 6 ] [ 333 ]
[ 2 ] [ 4 ] [ 2 ] [ 78 ] [ 23 ] [ 23 ] [ 35 ] [ 6 ] [ 324 ] [ 224 ] [ 6555 ] [ 333 ]
[ 2 ] [ 4 ] [ 2 ] [ 35 ] [ 6 ] [ 23 ] [ 78 ] [ 23 ] [ 324 ] [ 224 ] [ 6555 ] [ 333 ]
Step 2
[ 2 ] [ 4 ] [ 2 ] [ 35 ] [ 6 ] [ 23 ] [ 78 ] [ 23 ] [ 324 ] [ 224 ] [ 6555 ] [ 333 ]
[ 2 ] [ 4 ] [ 2 ] [ 23 ] [ 6 ] [ 23 ] [ 78 ] [ 35 ] [ 324 ] [ 224 ] [ 6555 ] [ 333 ]
Step 1
[ 2 ] [ 4 ] [ 2 ] [ 23 ] [ 6 ] [ 23 ] [ 78 ] [ 35 ] [ 324 ] [ 224 ] [ 6555 ] [ 333 ]
[ 2 ] [ 2 ] [ 4 ] [ 6 ] [ 23 ] [ 23 ] [ 35 ] [ 78 ] [ 224 ] [ 324 ] [ 333 ] [ 6555 ]
Array
(
[0] => 2
[1] => 2
[2] => 4
[3] => 6
[4] => 23
[5] => 23
[6] => 35
[7] => 78
[8] => 224
[9] => 324
[10] => 333
[11] => 6555
)