Selection sort

L'ordinamento per selezione (selection sort) è un algoritmo di ordinamento che opera in modo simile all'ordinamento per inserzione; seleziona il numero minore nella sequenza di partenza e lo sposta nella sequenza ordinata.

La complessità di tale algoritmo è dell'ordine di ${\frac {n(n-1)}{2}}={\frac {n^{2}-n}{2}}=O(n^{2})$

Esempio di implementazione in C

selection() {
  int i, j, min, t; 

  for (i=0; i < N-1; i++) {
    min = i;

    for (j= i + 1; j <= N; j++)
      if (a[j] < a[min]) min = j;

    t = a[min]; a[min] = a[i]; a[i] = t;
  }
}

Esempio di programma in Pascal

program SelectionSort(input,output);
const dim=20;
var a: array[1..dim] of integer;
    n,i,j,k,min,aux:integer;
begin
 // Creazione vettore di n elementi (con 1<=n<=dim)
 for i:=1 to n do begin
  min:=a[i];
  k:=i;
  for j:=(i+1) to n do
   if a[j]<min then begin
    min:=a[j];
    k:=j;
   end;
   aux:=a[i];
   a[i]:=a[k];
   a[k]:=aux;
  end;
 // Stampa del vettore
 readln;
end;