algorithm
선택 정렬

선택 기본 정보 정렬

선택 정렬 은 정렬 알고리즘, 특히 현재 위치 비교 정렬입니다. 그것은 O (n2) 시간의 복잡성을 가지고있어서 큰리스트에서는 비효율적이며 일반적으로 유사한 삽입 정렬보다 나쁘다. 선택 정렬은 단순성으로 유명하며 특정 상황에서 특히 보조 메모리가 제한적인 경우보다 복잡한 알고리즘보다 성능 이점이 있습니다.

알고리즘은 입력 목록을 두 부분으로 나눕니다. 이미 정렬 된 항목의 하위 목록 (목록의 앞 (왼쪽)에서 왼쪽에서 오른쪽으로 작성 됨)과 나머지 항목을 차지하는 정렬로 남아있는 항목의 하위 목록 명부. 처음에 정렬 된 하위 목록은 비어 있으며 정렬되지 않은 하위 목록은 전체 입력 목록입니다. 알고리즘은 정렬되지 않은 하위 목록에서 가장 작은 (또는 정렬 순서에 따라 가장 큰) 요소를 찾아 정렬되지 않은 가장 왼쪽 요소와 교환 (교체 순서)하고 하위 목록 경계를 한 요소만큼 오른쪽으로 이동함으로써 진행됩니다 .

선택 정렬을위한 의사 코드 :

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