PHPによるアルゴリズム ソート 改良挿入法（シェル・ソート）
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);
$gap = $count / 2;
while ($gap >= 1) {
for ($k=0; $k<$gap; $k++) {
for ($i=$k+$gap; $i<$count; $i=$i+$gap) {
for ($j=$i-$gap; $j>=$k; $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 / 2;
}
return $arr;
}
$arr = createRandArray(16);
sprint($arr);
$arr = shellSort($arr);
sprint($arr);
```
結果：
```
$ php shell.php
82 711 797 930 263 118 572 844 388 45 774 999 744 667 855 345
45 82 118 263 345 388 572 667 711 744 774 797 844 855 930 999
```