algorithm
Selezione Ordina
Ricerca…
Selezione Ordina informazioni di base
L'ordinamento della selezione è un algoritmo di ordinamento, in particolare un ordinamento di confronto sul posto. Ha una complessità di tempo O (n2), che lo rende inefficiente su elenchi di grandi dimensioni e, in genere, peggiora rispetto all'ordinamento di inserzione simile. L'ordinamento della selezione è noto per la sua semplicità e presenta vantaggi prestazionali rispetto ad algoritmi più complicati in determinate situazioni, in particolare quando la memoria ausiliaria è limitata.
L'algoritmo divide l'elenco di input in due parti: la sottolista di elementi già ordinati, che viene compilata da sinistra a destra nella parte anteriore (a sinistra) dell'elenco e la sottolista di elementi rimanenti da ordinare che occupano il resto della lista. elenco. Inizialmente, la sottolista ordinata è vuota e la sottolista non ordinata è l'intera lista di input. L'algoritmo procede trovando l'elemento più piccolo (o più grande, a seconda dell'ordine di ordinamento) nella sottolista non ordinata, scambiandolo (scambiandolo) con l'elemento non selezionato più a sinistra (inserendolo nell'ordine ordinato) e spostando i limiti di sottolista di un elemento a destra .
Pseudo codice per l'ordinamento Selezione:
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]
Visualizzazione del tipo di selezione:
Esempio di selezione Ordina:
Spazio ausiliario: O(n)
Complessità del tempo: O(n^2)
Implementazione della selezione sort in C #
Ho usato il linguaggio C # per implementare l'algoritmo Sort sort.
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;
}
}
Implementazione di elisir
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