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 ${\displaystyle {\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,pos,min,aus:integer;
begin
 // Creazione vettore di n elementi (con 1<=n<=dim)
 pos:=0; 
 for i:=1 to n-1 do begin
    min:= a[i];
    for j:=(i+1) to n do begin
      if a[j]< min then begin
        min:= a[j];
        pos:= j;
      end;
    end;
    aus:= a[i];
    a[i]:= min;
    a[pos]:= aus;
  end;
 // Stampa del vettore
 readln;
end;