algorithm
Auswahl sortieren

Auswahl sortieren Basisinformationen

Auswahlsortierung ist ein Sortieralgorithmus, insbesondere eine Direktvergleichssortierung. Es hat eine O (n2) -Zeitkomplexität, was es bei großen Listen ineffizient macht und im Allgemeinen schlechter abschneidet als die ähnliche Sortierreihenfolge. Die Auswahl der Auswahl ist für ihre Einfachheit bekannt und hat in bestimmten Situationen, insbesondere wenn der Hilfsspeicher begrenzt ist, Leistungsvorteile gegenüber komplizierteren Algorithmen.

Der Algorithmus teilt die Eingabeliste in zwei Teile auf: die Unterliste der bereits sortierten Elemente, die von links nach rechts am Anfang (links) der Liste aufgebaut ist, und die Unterliste der noch zu sortierenden Elemente, die den Rest der Liste belegen Liste. Anfangs ist die sortierte Unterliste leer und die unsortierte Unterliste ist die gesamte Eingabeliste. Der Algorithmus fährt damit fort, das kleinste (oder je nach Sortierreihenfolge größte) Element in der unsortierten Unterliste zu finden, es mit dem ganz linken unsortierten Element auszutauschen (zu sortieren) und die Unterlistengrenzen um ein Element nach rechts zu verschieben .

Pseudocode für Auswahl sortieren:

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]

Visualisierung der Auswahlart:

Beispiel für die Auswahl der Sortierung:

Hilfsraum: O(n)
Zeitkomplexität: O(n^2)

Implementierung der Auswahlsortierung in C #

Ich habe die C # -Sprache verwendet, um den Selection-Sortieralgorithmus zu implementieren.

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

Elixier-Implementierung

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