2020年10月15日に書いた記事です。
様々なアルゴリズムについて分かりやすいサイトを紹介しながら簡潔に紹介します。
アルゴリズムとは
問題を解決するための方法や手順のこと。問題解決の手続きを一般化するもので、プログラミングを作成する基礎となる。
出典 ASCII.jpデジタル用語辞典/ASCII.jpデジタル用語辞典について
簡単に言うと「効率的に問題を解くための手順や計算方法」です。
プログラミングを作成する基礎となるのがアルゴリズムであるため、アルゴリズムを習得することによってプログラミングスキルが向上するのは間違いなさそうです。
ソートアルゴリズム
ソートアルゴリズムとは、大量のデータを扱う際に昇順や降順でデータを並べ替えるアルゴリズムです。代表的なものは「バブルソート」「ヒープソート」「クイックソート」「マージソート」があります。
バブルソートとは、隣と比べて、逆順なら入れ替えるソートする方法です。
例：｛7, 8, 2, 5, 9, 6｝を昇順にソート
→｛7, 8, 2, 5, 6, 9｝ //6と9交換
→｛7, 2, 8, 5, 6, 9｝ //2と8交換
→｛2, 7, 8, 5, 6, 9｝ //2と7交換
→｛2, 7, 5, 8, 6, 9｝ //5と8交換
→｛2, 5, 7, 8, 6, 9｝ //5と7交換
→｛2, 5, 7, 6, 8, 9｝ //6と8交換
→｛2, 5, 6, 7, 8, 9｝ //6と7交換
特徴としては、
- 隣りの要素を大小比較しながら整列
- 単純なアルゴリズム
- あまり効率の良くないアルゴリズム
プログラミング言語(C言語)でのバブルソート
ヒープソート
ヒープソートはデータをヒープ構造といわれる2分木を構築して整列させる手法です。
ヒープソートの例でめちゃ分かりやすいサイトがあったので紹介します。
特徴としては、
- 親データが子のデータよりも小さくなるように作られた構造
- 常時根にはもっとも小さいデータ
- 平均的にクイックソートより遅い
プログラミング言語(C言語)でのヒープソート
クイックソート
クイックソートは列を2つに分割して、それぞれを整列していくソート方法です。
特徴としては、
- ソートアルゴリズムのなかで最も高速
- データの比較と交換回数が非常に少ない
- 対象のデータの並びやデータの数によっては必ずしも速いわけではない
プログラミング言語(C言語)でのクイックソート
マージソート
マージソートは、最初にリストを小さな単位に分け、2つのリストをそれぞれの要素の先頭を比較してマージし、最後までこの操作をくり返すとリストはソートされているという方法です。
例：｛7, 3, 8, 1, 5, 2, 4, 6｝を昇順にソート
→｛7, 3, 8, 1},{5, 2, 4, 6｝//分割
→｛7, 3} , {8, 1｝,{5, 2}, {4, 6｝
→｛7} , {3} , {8}, {1} , {5} , {2}, {4}, {6｝
→｛3, 7} , {1, 8｝,{2, 5}, {4, 6｝//併合
→｛1, 3, 7, 8},{2, 4, 5, 6｝
→｛1, 2, 3, 4, 5, 6, 7, 8｝
特徴としては、
- データを分割し各々をソート行った後にマージ
- 平均実行時間・最悪実行時間ともに計算が高速
プログラミング言語(C言語)でのクイックソート
探索アルゴリズム
探索アルゴリズムは、大量のデータの中から目的にあったものを探し出す時に使われるアルゴリズムです。代表的なものでは「線形探索」「二分探索」があります。
線形探索(リニアサーチ)
データを先頭から順番に調べていく手法。
<script>
var a = [5,3,1,4,2];
var search = 4;
var f = -1;
for (var i = 0; i < a.length; i++) {
if (a[i] == search) {
f = i;
break;
}
}
alert("番号="+ f);
</script>
で実行することによって番号=3が出力されます。
二分探索(バイナリサーチ)
木構造において、それぞれのレベルで2つうちのどちらかを選択すると最終的に欲しい解にたどり着けるという手法。
例)二分探索で1/4円を描画する(javascript)
function f(x, y){
return x * x + y * y - 1
}
function circle(p1, p2, level){
if (level == 0){
draw_rect(p1, p2)
return
}
var x1 = p1[0]; var y1 = p1[1]
var x2 = p2[0]; var y2 = p2[1]
var c1 = f(x1, y1)
var c2 = f(x1, y2)
var c3 = f(x2, y1)
var c4 = f(x2, y2)
if (c1 > 0 && c2 > 0 && c3 > 0 && c4 > 0 || c1 < 0 && c2 < 0 && c3 < 0 && c4 < 0)return
var mx = (x1 + x2) / 2
var my = (y1 + y2) / 2
var pm = [mx, my]
var pp1 = [mx, y1]
var pp2 = [x2, my]
var pp3 = [x1, my]
var pp4 = [mx, y2]
circle(p1, pm, level - 1)
circle(pm, p2, level - 1)
circle(pp1, pp2, level - 1)
circle(pp3, pp4, level - 1)
}
circle([0, 1], [1, 0], 9)
アルゴリズム計算時間
計算量はオーダーで表すことが多い。
| アルゴリズム | 最悪実行時間 | 平均実行時間 | 空間計算量 |
| セレクションソート | O(n^2) | O(n^2) | O(1) |
| バブルソート | O(n^2) | O(n^2) | O(1) |
| クイックソート | O(n^2) | O(n logn) | O(n) |
| ヒープソート | O(n logn) | O(n logn) | O(n logn) |
| マージソート | O(n logn) | O(n logn) | O(n) |