algorithm
Sélection Tri

Sélection Tri Informations de base

Le tri par sélection est un algorithme de tri, en particulier un tri de comparaison sur place. Il a une complexité temporelle de O (n2), ce qui le rend inefficace sur les grandes listes, et donne généralement de meilleurs résultats que le tri par insertion similaire. Le tri par sélection est connu pour sa simplicité et présente des avantages en termes de performances par rapport à des algorithmes plus compliqués dans certaines situations, en particulier lorsque la mémoire auxiliaire est limitée.

L'algorithme divise la liste d'entrée en deux parties: la sous-liste des éléments déjà triés, qui est construite de gauche à droite au début (gauche) de la liste, et la sous-liste des éléments restant à trier qui occupent le reste de la liste. liste. Initialement, la sous-liste triée est vide et la sous-liste non triée est la liste complète des entrées. L'algorithme procède en trouvant l'élément le plus petit (ou le plus grand, selon l'ordre de tri) dans la sous-liste non triée, en échangeant (échangeant) l'élément non trié le plus à gauche (en le triant) et en déplaçant les limites .

Pseudo-code pour le tri de sélection:

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]

Visualisation du tri de sélection:

Exemple de tri de sélection:

Espace auxiliaire: O(n)
Complexité temporelle: O(n^2)

Implémentation du tri par sélection en C #

J'ai utilisé le langage C # pour implémenter un algorithme de tri de sélection.

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

Mise en œuvre de l'élixir

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