algorithm
選択ソート

選択ソート基本情報

選択ソートはソートアルゴリズムです。具体的には、インプレース比較ソートです。 O（n2）時間の複雑さを伴い、大きなリストでは効率が悪く、一般的に同様の挿入方法より悪くなります。選択ソートはそのシンプルさから注目されており、特に補助メモリが限られている状況では、より複雑なアルゴリズムよりもパフォーマンス上の利点があります。

アルゴリズムは、入力リストを2つの部分に分割する。すなわち、既にソートされた項目のサブリストであり、リストの前（左）に左から右に構築され、残りの項目をソートする残りの項目のサブリストリスト。最初は、ソートされたサブリストは空であり、ソートされていないサブリストは入力リスト全体です。アルゴリズムは、ソートされていないサブリストの最小の（またはソート順に応じて最大の）要素を見つけ、ソートされていない要素の中で一番左の要素と交換（スワップ）し、サブリストの境界を右。

選択ソートの擬似コード：

function select(list[1..n], k)
 for i from 1 to k
     minIndex = i
     minValue = list[i]
     for j from i+1 to n
         if list[j] < minValue
             minIndex = j
             minValue = list[j]
     swap list[i] and list[minIndex]
 return list[k]

選択ソートの可視化：

選択ソートの例：

補助空間： O(n)
時間複雑度： O(n^2)

C＃での選択ソートの実装

選択ソートアルゴリズムを実装するためにC＃言語を使用しました。

public class SelectionSort
{
    private static void SortSelection(int[] input, int n)
    {
        for (int i = 0; i < n - 1; i++)
        {
            var minId = i;
            int j;
            for (j = i + 1; j < n; j++)
            {
                if (input[j] < input[minId]) minId = j;
            }
            var temp = input[minId];
            input[minId] = input[i];
            input[i] = temp;
        }
    }

    public static int[] Main(int[] input)
    {
        SortSelection(input, input.Length);
        return input;
    }
}

エリクシルの実装

defmodule Selection do

  def sort(list) when is_list(list) do
    do_selection(list, [])
  end

  def do_selection([head|[]], acc) do
    acc ++ [head]
  end

  def do_selection(list, acc) do
    min = min(list)
    do_selection(:lists.delete(min, list), acc ++ [min])
  end

  defp min([first|[second|[]]]) do
    smaller(first, second)
  end

  defp min([first|[second|tail]]) do
    min([smaller(first, second)|tail])
  end

  defp smaller(e1, e2) do
    if e1 <= e2 do
      e1
    else
      e2
    end
  end
end

Selection.sort([100,4,10,6,9,3])
|> IO.inspect