PHPによるアルゴリズム ソート 改良挿入法2（シェル・ソート）
2022-08-26
2022-08-26
説明
改良挿入法：
整列された部分数列に対し該当項目を適切な位置に挿入することを繰り返す。
アルゴリズム：
1,gap に初期値（N／２）を設定
2,gapが1になるまで以下を繰り返す
3,gapとびの部分数列は全部でgap個あるので、この回数だけ以下を繰り返す
4,gapとびの部分数列を基本挿入法でソートする
PHPソース：
```
<?php
/**
* 1000以内の乱数を生成する
*
* @param int $count
* @return array
*/
function createRandArray($count) {
$arr = [];
for ($i=0; $i<$count; $i++) {
$arr[] = mt_rand(1, 1000);
}
return $arr;
}
/**
* 表示
*
* @param array $arr
*/
function sprint($arr) {
foreach ($arr as $num) {
print("$num ");
}
print("\n");
}
/**
* ソート
*
* @param array $arr
* @return array
*/
function shellSort($arr) {
$count = count($arr);
for ($gap=1; $gap<$count/3; $gap=3*$gap+1) {}
while ($gap > 0) {
for ($i=$gap; $i<$count; $i++) {
for ($j=$i-$gap; $j>=0; $j=$j-$gap) {
if ($arr[$j] > $arr[$j+$gap]) {
$t = $arr[$j];
$arr[$j] = $arr[$j+$gap];
$arr[$j+$gap] = $t;
}
else {
break;
}
}
}
$gap = $gap / 3;
}
return $arr;
}
$arr = createRandArray(16);
sprint($arr);
$arr = shellSort($arr);
sprint($arr);
```
結果：
```
$ php shell2.php
368 976 830 512 606 916 358 777 634 349 560 684 147 425 712 679
147 349 358 368 425 512 560 606 634 679 684 712 777 830 916 976
```