選択ソート

今本当にやるべきことではないかもしれないが、基本的なアルゴリズムの勉強。

今日は選択ソート。

選択ソート

まず、 選択ソートとは線形探索のアルゴリズムをもとにして、 最小値を探し出していくアルゴリズム。

うかる! 基本情報技術者 [午後・アルゴリズム編] 2018年版 (福嶋先生の集中ゼミ)

この本の選択ソートのフローチャートとにらめっこして理解したうえで

Pythonで体験してわかるアルゴリズムとデータ構造

この本の三章を写経した。その後理解しているかどうか試すために、C#の練習がてらC#で書き下ろした。

ポイントとしては、 ①比較する方と②比較される方のループを実行する。 配列Aの要素数をNとすると、①比較する方のループは配列Aの最初からN-1までで、対して、②比較される方のループは配列Aのイテレーター+1からNまで。

ループの計算量はO(N)。そして、選択ソートでは①比較する方と②比較される方の二つのループを実行するから、O(N*N)。なので、選択ソートの計算量はO(N²)になる。

ちなみにうかる！基本情報技術者試験午後のほうの選択ソートのフローチャート（P144）、最後の条件文って要るのか...??無くても動いたけど理由がわからん...。

Python3.8

二つの変数a,bの値の交換をするときは、一時的に値を代入するtempのような変数が必要。

temp = b
b = a
a = temp

しかしPythonでは変数tempに一時的に値を置かずに値の交換をa,b = b,aと一行で済ませることができる。やっぱりpythonは書きやすいなあ。

l = [2,3,4,1,6,7,8,9,5]

def sort(A):
    for i in range(0,len(A)-1):
        select_min(A, i)

def select_min(A, i):
    min = i
    for j in range(i+1, len(A)):
        if A[min] > A[j]:
            min = j
    A[i], A[min] = A[min], A[i]


sort(l)
print(l)

#[1, 2, 3, 4, 5, 6, 7, 8, 9]

Wandboxでのコードはこちら

C#5.19

public class SelectionSort{
    public static void Main(){
        int[] arr = {2,3,4,1,6,7,8,9,5};

        Sort(arr);

        for (int i = 0; i < arr.Length-1; i++)
        {
            System.Console.Write(arr[i]);    
        }
        
        
    }

    private static void Sort(int[] A)
    {
        for (int i = 0; i < A.Length - 1; i++)
        {
            SelectMin(A, i);
        }
    }

    private static void SelectMin(int[] A, int i)
    {
        int min = i;

        for (int j = i + 1; j < A.Length; j++)
        {

            if (A[min] > A[j])
            {
                min = j;
            }
        }

        int temp = A[i];
        A[i] = A[min];
        A[min] = temp;

    }
}

//12345678

Wandboxでのコードはこちら

あまりC#は書けないのだけど、System.Console.Write(arr)で配列は出力されないで一々for文回してあげないといけないのね...。