PHPによるアルゴリズム ソート 基本交換法（シェーカー・ソート）
2022-08-26
2022-08-26
説明
基本交換法（シェーカー・ソート）：
バブル・ソートでは部分数列が正しく並んでいたとしても、全部を比較を繰り返しているため、効率が悪いです。
それを解消するためのソート法は シェーカー・ソートです。
アルゴリズム：
左と右両方から、隣接２項目を比較し、後ろの項目が前の項目より小さければ、両項目の入れ替えを行い、
最終入れ替えの位置をshiftに記憶しておき、左からのshiftは右からのshiftより小さければ、
処理を繰り返する
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 shakerSort($arr) {
$left = 0;
$right = count($arr) - 1;
while ($left < $right) {
for ($i=$left; $i<$right; $i++) {
if ($arr[$i] > $arr[$i+1]) {
$t = $arr[$i];
$arr[$i] = $arr[$i+1];
$arr[$i+1] = $t;
$shift = $i;
}
}
$right = $shift;
for ($i=$right; $i>$left; $i--) {
if ($arr[$i] < $arr[$i-1]) {
$t = $arr[$i];
$arr[$i] = $arr[$i-1];
$arr[$i-1] = $t;
$shift = $i;
}
}
$left = $shift;
}
return $arr;
}
$arr = createRandArray(10);
sprint($arr);
$arr = shakerSort($arr);
sprint($arr);