PHPによるアルゴリズム ソート 基本挿入法
2022-08-26
2022-08-26
説明
基本挿入法：
整列された部分数列に対し該当項目を適切な位置に挿入することを繰り返す。
アルゴリズム：
１、対象項目は i を ０〜N-2 移しながら、以下を繰り返す。
対象項目はその前の整列された部分数列の適切な位置に挿入する。
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 insertSort($arr) {
for ($i=0; $i<count($arr); $i++) {
for ($j=$i-1; $j>=0; $j--) {
if ($arr[$j] > $arr[$j+1]) {
$t = $arr[$j];
$arr[$j] = $arr[$j+1];
$arr[$j+1] = $t;
}
else {
break;
}
}
/* 以下のソースも可
$t = $arr[$i];
for ($j=$i-1; $j>=0 && $arr[$j]>$t; $j--) {
$arr[$j+1] = $arr[$j];
}
$arr[$j+1] = $t;
*/
}
return $arr;
}
$arr = createRandArray(10);
sprint($arr);
$arr = insertSort($arr);
sprint($arr);
```
結果：
```
$ php insert.php
595 163 914 868 907 371 599 509 634 623
163 371 509 595 599 623 634 868 907 914
```