algorithm
Urvalssortering

Val Sortera grundläggande information

Urvalssortering är en sorteringsalgoritm, speciellt en jämförelse på plats. Den har O (n2) tidskomplexitet, vilket gör den ineffektiv på stora listor och fungerar generellt sämre än den liknande insättningssorten. Urvalssortering är känd för sin enkelhet och har prestandafördelar jämfört med mer komplicerade algoritmer i vissa situationer, särskilt där hjälpminnet är begränsat.

Algoritmen delar inmatningslistan i två delar: underlistan över objekt som redan har sorterats, som är uppbyggd från vänster till höger framtill (vänster) på listan, och sublistan över objekt som återstår att sorteras som upptar resten av lista. Ursprungligen är den sorterade underlistan tom och den osorterade underlistan är hela inmatningslistan. Algoritmen fortsätter genom att hitta det minsta (eller största, beroende på sorteringsordning) -elementet i den osorterade underlistan, utbyta (byta) det med det vänstra osorterade elementet (sätta det i sorterad ordning) och flytta sublistgränserna ett element till höger .

Pseudokod för urvalssortering:

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]

Visualisering av urvalssortering:

Exempel på urvalssortering:

Hjälprum: O(n)
Tidskomplexitet: O(n^2)

Implementering av urvalssortering i C #

Jag använde C # -språket för att implementera urvalssorteringsalgoritmen.

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;
    }
}

Elixir-implementering

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