algorithm
Selección de selección

Selección Ordenar Información Básica

La selección de selección es un algoritmo de clasificación, específicamente una clasificación de comparación in situ. Tiene una complejidad de tiempo O (n2), lo que la hace ineficiente en listas grandes y, en general, tiene un rendimiento peor que el orden de inserción similar. El orden de selección se destaca por su simplicidad y tiene ventajas de rendimiento sobre algoritmos más complicados en ciertas situaciones, particularmente cuando la memoria auxiliar es limitada.

El algoritmo divide la lista de entrada en dos partes: la lista secundaria de elementos ya ordenados, que se construye de izquierda a derecha en la parte delantera (izquierda) de la lista, y la lista secundaria de elementos pendientes de clasificación que ocupan el resto de la lista. lista. Inicialmente, la lista secundaria ordenada está vacía y la lista secundaria sin clasificar es la lista de entrada completa. El algoritmo procede al encontrar el elemento más pequeño (o más grande, según el orden de clasificación) en la lista secundaria sin clasificar, intercambiarlo (intercambiarlo) con el elemento sin clasificar más a la izquierda (ordenándolo) y mover los límites de la lista secundaria un elemento a la derecha .

Pseudo código para selección de selección:

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]

Visualización del orden de selección:

Ejemplo de selección por selección:

Espacio auxiliar: O(n)
Complejidad del tiempo: O(n^2)

Implementación del ordenamiento de selección en C #

Utilicé el lenguaje C # para implementar el algoritmo de selección de selección.

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

Implementación de Elixir

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