algorithm
Selectie sorteren

Selectie Sorteren Basisinformatie

Selectie sorteren is een sorteeralgoritme, specifiek een interne sorteersoort. Het heeft een O (n2) tijdcomplexiteit, waardoor het in grote lijsten inefficiënt is en over het algemeen slechter presteert dan de vergelijkbare invoegsoort. Selectie sorteren staat bekend om zijn eenvoud, en het heeft prestatievoordelen ten opzichte van meer gecompliceerde algoritmen in bepaalde situaties, met name wanneer het hulpgeheugen beperkt is.

Het algoritme verdeelt de invoerlijst in twee delen: de sublijst van items die al zijn gesorteerd, die van links naar rechts is opgebouwd aan de voorzijde (links) van de lijst, en de sublijst van items die nog moeten worden gesorteerd en die de rest van de lijst. Aanvankelijk is de gesorteerde sublijst leeg en is de ongesorteerde sublijst de volledige invoerlijst. Het algoritme gaat verder door het kleinste (of grootste, afhankelijk van de sorteervolgorde) element in de ongesorteerde sublijst te vinden, het uit te wisselen (ruilen) met het meest linkse ongesorteerde element (het in gesorteerde volgorde te plaatsen) en de sublijstgrenzen één element naar rechts te verplaatsen .

Pseudo-code voor selectie sorteren:

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]

Visualisatie van selectie sorteren:

Voorbeeld van selectie sorteren:

Hulpruimte: O(n)
Tijd Complexiteit: O(n^2)

Implementatie van selectie sorteren in C #

Ik heb C # -taal gebruikt om het selectie-sorteeralgoritme te implementeren.

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-implementatie

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