アルゴリズムの授業1回目のノート
！注意！
本ページ内のサンプルコードはChatGPTで生成したものです。正確性の保証はありません。
個人的に授業がPythonでわけが分からないよ状態だったので、C#版のコードを作ってもらったものです。文明は偉大。AI最高！AI最高！まぁC#も別にメチャクチャわかるとかじゃないんですが・・・。励みます。
もし記事内に間違えがあれば指摘してもらえると嬉しいです。
このNoteはどういう記事？
この記事は私が授業で眠っちゃわないように書いているObsidianのページをそのまま持ってきたものです。
あまり参考にされても困るので、「こいつ頑張っとるやん」くらいな仏の目線で眺めてもらえたらうれしいです。
あと、画像等をUdemyメディアから引用してます。
リンクを張るので、リファレンス探しで訪ねてきた方。即リンクで飛びましょう。何なら講義を買っちまいましょう。Udemyは良いぞ(ガチ)
↓リンク↓
アルゴリズムとは？
アルゴリズム ＝ 計算方法 と言えます。
ある課題を解決する際の手順はざっくり3段階に分かれます。
問題を理解する
→解決すべき問題を正確にとらえる。アルゴリズムの考案、選択
→アルゴリズムは必ずしも考案しなければならないわけではない。
→知っているアルゴリズムで解決できるなら、選択してあとはコードを書けばいい。コーディング
→アルゴリズムを適用してコードを書く。
アルゴリズムの優劣とは
同じ問題を解くためのアルゴリズムは複数存在することが多いです。
その際何を基準にして選ぶのか？
優劣を決める要素
計算量の量
メモリの利用量の量
プログラムの簡潔性。
計算に使う時間は短い方がいい。メモリは実行環境の制約によって変わる。上記2つのポイントで拮抗したら？そりゃ楽な方を取るに決まってる。
楽したいからと言って3を優先して膨大な計算量、メモリの使用量になっちゃ意味がないよね！
データ構造とは？
データ構造とは、データを効率的に整理するための整理法と言い換えることができます。
配列、変数、Dictionary、Listなどが該当します。要は値を格納する仕組みってこと。
サーチについて
リニアサーチ
C#のForeachなどがリニアサーチを機能化したものです。
配列を先頭から比較、チェックしていき、対象が見つかるまで繰り返します。
注意！
大きすぎるデータ相手には処理に非常に時間がかかってしまうという弱点があります！
サンプルコード
手動で行った場合
using System;
class Program
{
static void Main()
{
int[] array = { 3, 5, 7, 9, 11 }; // 配列を初期化
int target = 7; // 探したい値
int index = LinearSearch(array, target); // リニアサーチを呼び出し
if (index != -1)
Console.WriteLine($"Element found at index: {index}"); // 見つかった場合
else
Console.WriteLine("Element not found"); // 見つからなかった場合
}
static int LinearSearch(int[] arr, int target)
{
for (int i = 0; i < arr.Length; i++) // 配列を走査
{
if (arr[i] == target) // 値が見つかった場合
return i; // インデックスを返す
}
return -1; // 見つからなかった場合、-1を返す
}
}
Foreachを使用した場合
using System;
class Program
{
static void Main()
{
int[] array = { 3, 5, 7, 9, 11 }; // 配列を初期化
int target = 7; // 探したい値
int index = LinearSearch(array, target); // リニアサーチを呼び出し
if (index != -1)
Console.WriteLine($"Element found at index: {index}"); // 見つかった場合
else
Console.WriteLine("Element not found"); // 見つからなかった場合
}
static int LinearSearch(int[] arr, int target)
{
int index = 0; // 現在のインデックスを追跡
foreach (var item in arr) // 配列を走査
{
if (item == target) // 値が見つかった場合
return index; // インデックスを返す
index++; // インデックスをインクリメント
}
return -1; // 見つからなかった場合、-1を返す
}
}
バイナリサーチ
例えば、0～9の値が入った配列があるとします。
バイナリサーチは中央の値と探したい値を比較し、大きいか小さいかを比較します。
たとえば探したい数が8の場合、5と比較すると8のほうが大きいです。つまり、5~9以外をサーチ対象から外せます。
これを繰り返すことで探索範囲をどんどん絞っていくことで高速で探したい対象を見つけることができます。
注意
このアルゴリズムは「データに規則性がある場合のみ使える」という縛りがあります。
なので、数値がランダムに入った配列などには適用できない弱点があります。
→ソートを行ってからバイナリサーチを使う必要がある。
サンプルコード
using System;
class Program
{
static void Main()
{
int[] array = { 1, 3, 5, 7, 9, 11, 13 }; // ソート済みの配列を初期化
int target = 7; // 探したい値
int index = BinarySearch(array, target); // バイナリサーチを呼び出し
if (index != -1)
Console.WriteLine($"Element found at index: {index}"); // 見つかった場合
else
Console.WriteLine("Element not found"); // 見つからなかった場合
}
static int BinarySearch(int[] arr, int target)
{
int left = 0; // 検索範囲の左端
int right = arr.Length - 1; // 検索範囲の右端
while (left <= right) // 検索範囲が有効である限りループ
{
int middle = (left + right) / 2; // 中央のインデックスを計算
if (arr[middle] == target) // 値が見つかった場合
return middle; // インデックスを返す
else if (arr[middle] < target) // 目的の値が中央の値よりも大きい場合
left = middle + 1; // 検索範囲を右側に移動
else // 目的の値が中央の値よりも小さい場合
right = middle - 1; // 検索範囲を左側に移動
}
return -1; // 見つからなかった場合、-1を返す
}
}
基本のソートのアルゴリズム
先に一つ。バブルソート、選択サーチ、挿入サーチの三つを先に書きましたが、どれも計算時間は同じらしい。で、どれも遅くて使えたものではないのだそう。
この3つの後に説明するより本格的なソートプログラムを使うのだそうです。ちなみにそのちゃんとしたソートアルゴリズムは次の授業だそう。今回はありません！残念！
バブルソート
先頭の2つを比較して、大きい方を右に移動、さらに隣で比較…と繰り返していき、対象の数字が比較した数より小さくなるまで繰り返す・・・。これをひたすら繰り返すことで大きい順に数値を並べていくのが数値の降順ソート。A-Zなども同じ要領(のはず)。
サンプルコード
using System;
class Program
{
static void Main()
{
int[] array = { 34, 7, 23, 32, 5, 62 }; // ソートする配列を初期化
BubbleSort(array); // バブルソートを呼び出し
// ソートされた配列を出力
foreach (var item in array)
{
Console.Write(item + " ");
}
}
static void BubbleSort(int[] arr)
{
int n = arr.Length; // 配列の長さを取得
bool swapped; // 交換が発生したかどうかを追跡
/*
do - Whileは条件が何であろうと最初の1回だけは内部の処理を走らせる処理。
書式は下のコードを参考に。doの下に内部処理を書いて、その下にwhileのステートメントを書けばいいのかな？多分。
*/
do
{
swapped = false; // 交換フラグをリセット
for (int i = 0; i < n - 1; i++) // 配列を走査
{
if (arr[i] > arr[i + 1]) // 隣接する要素を比較
{
// 交換が必要な場合
int temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
swapped = true; // 交換フラグを設定
}
}
} while (swapped); // 交換が発生していない限り続行
}
}
バイナリサーチは上記のソートを先にやらないと使えないってことですね。( ..)φﾒﾓﾒﾓ
選択サーチ
はじめにデータ内をサーチして最大値か最大値を探して一番左 or 右に配置し、それ以降同じことをひたすら繰り返すという方法。
→リニアサーチを連打する感じっぽい。
不安定で低速なアルゴリズムという扱いみたいです。
サンプルコード
using System;
class Program
{
static void Main()
{
int[] array = { 29, 10, 14, 37, 13 }; // ソートする配列を初期化
SelectionSort(array); // 選択ソートを呼び出し
// ソートされた配列を出力
foreach (var item in array)
{
Console.Write(item + " ");
}
}
static void SelectionSort(int[] arr)
{
int n = arr.Length; // 配列の長さを取得
for (int i = 0; i < n - 1; i++) // 未ソートの部分を走査
{
int minIndex = i; // 最小値のインデックスを初期化
for (int j = i + 1; j < n; j++) // 最小値を見つける
{
if (arr[j] < arr[minIndex])
minIndex = j;
}
// 最小値を未ソートの部分の先頭と交換
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
}
挿入ソート
既にソート済みの部分をソートができていない部分を比較してソート済み部分のどこに入れるかを比較処理して適切な場所に挿入する。って感じらしいです。
挿入ソートはある程度並びがそろっているコードに対しては割と高速で動作するみたい。
なので、組み合わせ次第では使えないこともないみたい？
サンプルコード
using System;
class Program
{
static void Main()
{
int[] array = { 34, 7, 23, 32, 5, 62 }; // ソートする配列を初期化
InsertionSort(array); // 挿入ソート関数を呼び出し
// ソートされた配列を出力
foreach (var item in array)
{
Console.Write(item + " ");
}
}
static void InsertionSort(int[] arr)
{
int n = arr.Length; // 配列の長さを取得
for (int i = 1; i < n; i++) // 未ソートの部分を走査（インデックス 1 から開始）
{
int key = arr[i]; // 現在の要素をキーとして保存
int j = i - 1; // ソート済みセクションの最後のインデックスを取得
// キーをソート済みのセクションに挿入
while (j >= 0 && arr[j] > key) // キーがソート済みセクションの要素より小さい限り
{
arr[j + 1] = arr[j]; // ソート済みセクションの要素を右にシフト
j = j - 1; // ソート済みセクションのインデックスを減らす
}
arr[j + 1] = key; // キーを正しい位置に挿入
}
}
}
思ったことメモ
普段C#などC系を扱っているので、Python動的型付け言語の挙動や構文が慣れない。メチャクチャ違和感がある。
特に2//5とか。ダブルスラッシュで小数点切り捨てらしいけど、コメントにしか見えない・・・。慣れねば・・・。
Pythonだとa[R],a[L] = a[L],a[R]みたいな書き方で左右の交換ができるらしい。クソ便利か？
今回はここまでです。
授業の受け方はいまだによくわかってません。受けた方の方法についてトライアンドエラーを繰り返していくのでよろしくお願いします<(_ _)>
この記事が気に入ったらサポートをしてみませんか？