TechNote

とあるエンジニアのただのメモ

プログラムで簡単理解! 7つの超重要な整列アルゴリズム(ソートアルゴリズム)まとめ

基本情報技術者試験応用情報技術者試験の時期も近まった今、あらためて整列アルゴリズムをまとめてみたので、備忘録を兼ねてメモを残します。
即席コードも併せて記載しました。最低限のプログラムを読める方はこちらを読んだほうが理解しやすいかも知れません。PHPで書いてますが、どの言語にも読み換えがきく簡単なものです。
f:id:kojikoji75:20150801222832j:plain

世界でもっとも強力な9のアルゴリズム

世界でもっとも強力な9のアルゴリズム



整列アルゴリズムとは?


1列に並べられたデータをある規則に従って並べ替える処理を整列(ソート)といいます。

整列アルゴリズムには大きく7つあります。

1.バブルソート
2.選択ソート
3.挿入ソート
4.クイックソート
5.ヒープソート
6.シェルソート
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
}
(5)ヒープソート(選択ソートの発展Ver)


長くなりそうなので別エントリーで書きたいと思います。

取り急ぎCodeZineなどが参考になると思います。



(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
}
(7) マージソート
  • かなり高速
  • メモリを多く必要とする


こちらも長くなりそうなので、別エントリーで書きたいと思います。
取り急ぎ、CodeZineなどが参考になりそうです。

あわせて読みたい

一度は観ておきたい!エンジニアが主役の映画5選 (とそこで使われている技術を少々) - TechNote一度は観ておきたい!エンジニアが主役の映画5選 (とそこで使われている技術を少々) - TechNote

以前から一度まとめてみたかったタイトルの件、今更ながらまとめておきます。観たい映画がなくなった方や、エンジニアとして働いてるけど目標を見失ったという方のご参考に...

プログラマなら早めに読むべき! 良いコードを書くためによむべき本 8選 - TechNoteプログラマなら早めに読むべき! 良いコードを書くためによむべき本 8選 - TechNote

本件まとめたことなかったので、あえて今まとめてみます。読んでないものがあったら夏の終わりの一品としていかがでしょうか?Code Complete(上)(下)- ...

機嫌が悪いときほど人はクリエイティブになるのか? - TechNote機嫌が悪いときほど人はクリエイティブになるのか? - TechNote

機嫌が悪いときほど人...


入門 データ構造とアルゴリズム

入門 データ構造とアルゴリズム

C言語による最新アルゴリズム事典 (ソフトウェアテクノロジー)

C言語による最新アルゴリズム事典 (ソフトウェアテクノロジー)