プログラミングの心臓部！アルゴリズムの世界へようこそ【Go言語で学ぶ】 プログラミングを学び始めると、必ず出会うのが「アルゴリズム」という言葉です。なんだか難しそう…と感じるかもしれませんが、実はプログラミングの面白さと奥深さが詰まった、とても重要な概念なんです。
このブログでは、プログラミング初心者の方にも分かりやすく、様々なアルゴリズムをGo言語のサンプルコード付きで紹介していきます。アルゴリズムの世界を一緒に探検しましょう！ 🚀
アルゴリズムって、そもそも何？
アルゴリズムとは、一言でいうと「問題を解決するための一連の手順や計算方法」のことです。料理のレシピを思い浮かべてみてください。美味しいカレーを作るためには、「材料を切る」「炒める」「煮込む」といった決まった手順がありますよね。この手順が、プログラミングにおけるアルゴリズムにあたります。
効率的なアルゴリズムを使えば、コンピュータはより速く、より正確に問題を解決できます。逆に、非効率なアルゴリズムでは、簡単な問題でも膨大な時間がかかってしまうことがあります。だからこそ、アルゴリズムを理解することが、良いプログラマーになるための鍵となるのです。
基本の「ソート」アルゴリズム：バブルソート
まずは、たくさんのアルゴリズムの中でも基本中の基本、「ソート（整列）」アルゴリズムから見ていきましょう。ソートとは、バラバラのデータを特定の順序（例えば、小さい順や大きい順）に並べ替えることです。
今回は、最もシンプルで理解しやすい「バブルソート」を紹介します。
バブルソートの仕組み
バブルソートは、隣り合う要素を比較して、順序が逆であれば交換していく、という処理を繰り返します。まるで泡（バブル）が水面に上がっていくように、大きい（または小さい）要素が端に移動していく様子からこの名前が付きました。
手順
- リストの左端から右端へ、隣り合う2つの要素を比較する。
- 左の要素が右の要素より大きければ、2つを交換する。
- リストの右端までこれを繰り返す。この時点で、一番大きい要素が一番右に移動している。
- 今度は、一番右の要素を除いた範囲で、同じことを繰り返す。
- リスト全体がソートされるまで、この処理を繰り返す。
Goでのサンプルコード
package main import "fmt" func bubbleSort(arr []int) { n := len(arr) for i := 0; i < n-1; i++ { for j := 0; j < n-i-1; j++ { // 隣り合う要素を比較し、 // 左が右より大きければ交換する if arr[j] > arr[j+1] { arr[j], arr[j+1] = arr[j+1], arr[j] } } } } func main() { data := []int{64, 34, 25, 12, 22, 11, 90} fmt.Println("ソート前の配列:", data) bubbleSort(data) fmt.Println("ソート後の配列:", data) }
実行結果
ソート前の配列: [64 34 25 12 22 11 90] ソート後の配列: [11 12 22 25 34 64 90]
バブルソートはシンプルですが、データの件数が多くなると処理時間が非常に長くなるという弱点もあります。これを表す指標として計算量という考え方があり、バブルソートの平均計算時間は$O(n2)$と表されます。
効率的な「探索」アルゴリズム：二分探索
次に紹介するのは、何かを探すための「探索」アルゴリズムです。その中でも非常に高速な「二分探索（バイナリサーチ）」を見ていきましょう。
二分探索の仕組み
二分探索は、ソート済みのリストから目的のデータを探すためのアルゴリズムです。辞書で単語を探す時、真ん中あたりを開いて、目的の単語が前半にあるか後半にあるか見当をつけ、探す範囲を半分に絞り込んでいくと思います。二分探索は、まさにこの方法をコンピュータで行います。
手順
- リストの中央の要素を見つける。
- 中央の要素が探している値と一致すれば、探索は終了。
- 中央の要素が探している値より大きい場合、リストの左半分に範囲を絞って探索を続ける。
- 中央の要素が探している値より小さい場合、リストの右半分に範囲を絞って探索を続ける。
- 値が見つかるか、探す範囲がなくなるまで、この処理を繰り返す。
この方法により、探すたびに調査範囲が半分になるため、非常に効率的に目的のデータを見つけることができます。こちらの計算量は$O(\log n)$となり、バブルソートよりも格段に高速です。
Goでのサンプルコード
package main import "fmt" // 二分探索（バイナリサーチ） func binarySearch(arr []int, target int) int { low := 0 high := len(arr) - 1 for low <= high { mid := low + (high-low)/2 if arr[mid] == target { return mid // 値が見つかった場合、そのインデックスを返す } if arr[mid] < target { low = mid + 1 // 中央値より大きい場合、右半分を探索 } else { high = mid - 1 // 中央値より小さい場合、左半分を探索 } } return -1 // 値が見つからなかった場合 } func main() { // 二分探索はソート済みの配列が前提 data := []int{11, 12, 22, 25, 34, 64, 90} target := 25 result := binarySearch(data, target) if result != -1 { fmt.Printf("%d はインデックス %d に見つかりました。\n", target, result) } else { fmt.Printf("%d は配列内に見つかりませんでした。\n", target) } }
実行結果
25 はインデックス 3 に見つかりました。
まとめ
今回は、数あるアルゴリズムの中から、基本となる「バブルソート」と「二分探索」を紹介しました。
アルゴリズムを学ぶことは、単にコードの書き方を覚えるだけでなく、「どうすればもっと効率的に問題を解決できるか」という論理的思考力を鍛えることに繋がります。
今回紹介した以外にも、世の中にはたくさんの素晴らしいアルゴリズムが存在します。ぜひ、色々なアルゴリズムに触れて、プログラミングの奥深い世界を楽しんでください！
