基本情報技術者試験や応用情報技術者試験の時期も近まった今、あらためて整列アルゴリズムをまとめてみたので、備忘録を兼ねてメモを残します。
即席コードも併せて記載しました。最低限のプログラムを読める方はこちらを読んだほうが理解しやすいかも知れません。PHPで書いてますが、どの言語にも読み換えがきく簡単なものです。
整列アルゴリズムとは?
1列に並べられたデータをある規則に従って並べ替える処理を整列(ソート)といいます。
整列アルゴリズムは、大きくはバブルソート、選択ソート、挿入ソート、クイックソート、ヒープソート、シェルソート、マージソートの7つがあります。目的は同じ「整列」ですが、方法によってスピードやメモリ使用量などが異なってきます。
では、単純にスピードとメモリ使用量の兼ね合いから選択するのかというと、そういうことでもありません。
例えばC言語の関数にqsort(クイックソート)というのがあります。これはランダムに整列しているデータには強い効果を発揮しますが、ほぼ整列しているデータには相当な時間がかかる、という特徴があります。
要はアルゴリズムを知っていると、「これはこのパターンに強い」ということがわかるということです。
実生活で必要になることはまずないと思われますが、基本情報技術者試験や応用情報技術者試験を受験予定の方、コンピュータサイエンスを学習している人には必須の知識です。また、その辺りの学習を手抜きしたまま業務プログラマになった方なども知っていて損はない知識です。
(1)バブルソート
- 隣り合う要素の値を比較し、大小が逆だったら交換する。この比較を必要がなくなるまで繰り返す方法。
- 泡のようにデータが浮かび上がっていくので「バブルソート」。
$arry=array(9,2,8,3,7,4,6,5,1); $length=count($arry); for($j=0;$j<$length-1;$j++){ for($i=0;$i<$length-1;$i++){ if($arry[$i]>$arry[$i+1]){ $tmp = $arry[$i]; $arry[$i] = $arry[$i+1]; $arry[$i+1] = $tmp; } } } //画面表示 for($i=0;$i<$length;$i++){ echo $arry[$i]; //出力結果は123456789 }
(2)選択ソート
最小値を入れておく箱を一つ決めておく。そこに適当に一番左の値を入れ、順に比較していき小さいほうを箱にいれる。これを繰り返していく。
$arry=array(9,2,8,3,7,4,6,5,1); $length=count($arry); for($i=0;$i<$length;$i++){ $k = $i; $min = $arry[$i]; for($j=$i+1;$j<$length;$j++){ if($min > $arry[$j]){ $k = $j; $min = $arry[$j]; } } $arry[$k] = $arry[$i]; $arry[$i] = $min; } //画面表示 for($i=0;$i<$length;$i++){ echo $arry[$i]; //出力結果は123456789 }
(3)挿入ソート
$arry=array(9,2,8,3,7,4,6,5,1); $length=count($arry); for($i=0; $i<$length; $i++){ $tmp = $arry[$i]; for($k=$i; $k>0 && $arry[$k-1] > $tmp; $k--){ $arry[$k] = $arry[$k-1]; } $arry[$k] = $tmp; } // 結果出力 for($i=0; $i<$length; $i++){ echo $arry[$i]; //出力結果は123456789 }
(4)クイックソート(バブルソートの発展Ver)
- 基準値を決めて、大小のグループに分ける。基準値は何でもよい。
- 真ん中の位置にある値を基準値に決めたりする。
- ちなみにC言語のqsortは最後の値を基準値としている。
- 基準値より小さいグループと、基準値より大きいグループに分ける。
- お互いのグループの、条件に合ってない値を交換していく。
- できたグループ内でさらに同じ処理を繰り返していく。
- 再帰(同じプログラムquicksortを何度も利用)
$arry = array(9,2,8,3,7,4,6,5,1); $length = count($arry); q_sort($arry,0,$length-1); function q_sort(&$arr,$left,$right){ if($left>=$right){ return; } $key = (int) ($left+$right)/2; $pivot = $arr[$key]; $i = $left; $j = $right; while($i<=$j){ while($arr[$i]<$pivot){ $i++; } while($arr[$j]>$pivot){ $j--; } if($i<=$j){//一度交換すると$i>$jとなる場合があるので、その場合は交換しない $tmp = $arr[$i]; $arr[$i] = $arr[$j]; $arr[$j] = $tmp; $i++; $j--; } } q_sort($arr,$left,$j); q_sort($arr,$i,$right); } //画面表示 for($i=0;$i<$length;$i++){ echo $arry[$i]; //出力結果は123456789 }
(6)シェルソート(挿入ソートの発展Ver)
- とびとびのところを見ながら挿入ソート
- どんなデータでもそれなりのスピードで並べ替えてくれる。
$arry = array(9,2,8,3,7,4,6,5,1); $length = count($arry); for($h= (int) $length/2;$h>0;$h= (int) $h/2){ for($k=0;$k<$h;$k++){ for($i=$k+$h;$i<$length;$i+=$h){ $x = $arry[$i]; for($j=$i-$h;$j>=$k&&$arry[$j]>$x;$j-=$h){ $arry[$j+$h] = $arry[$j]; } $arry[$j+$h] = $x; } } } //画面表示 for($i=0;$i<$length;$i++){ echo $arry[$i]; //出力結果は123456789 }