Selection sort: differenze tra le versioni

Versione delle 19:09, 6 dic 2005

Versione attuale delle 09:42, 24 mar 2025

(190 versioni intermedie di oltre 100 utenti non mostrate)

Riga 1:

{{Algoritmo

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

|classe = [[Algoritmo di ordinamento]]

|immagine = Sorting selection sort anim.gif

|didascalia = Animazione dell'algoritmo che ordina dei numeri casuali

|struttura dati = [[Array]]

|tempo = ''O(n²)''

|tempo migliore = ''O(n²)''

|tempo medio = ''O(n²)''

|spazio = ''O(n)'' totale<br />''O(1)'' ausiliario

|ottimale = No

}}

L{{'}}'''ordinamento per selezione''' ('''selection sort''') è un [[algoritmo di ordinamento]] che opera [[Algoritmo in loco|in place]] ed in modo simile all'[[insertion sort|ordinamento per inserzione]]. L'algoritmo è di tipo non adattivo, ossia il suo tempo di esecuzione non dipende dall'input ma dalla dimensione dell'array.

== Descrizione dell'algoritmo ==

I passi sono i seguenti:

L'algoritmo ''seleziona'' di volta in volta il numero minore nella sequenza di partenza e lo sposta nella sequenza ordinata; di fatto la sequenza viene suddivisa in due parti: la sottosequenza ordinata, che occupa le prime posizioni dell'array, e la sottosequenza ''da'' ordinare, che costituisce la parte restante dell'array.

{|

|

Dovendo ordinare un array ''A'' di lunghezza ''n'', si fa scorrere l'indice ''i'' da 1 a ''n-1'' ripetendo i seguenti passi:

# si cerca il più piccolo elemento della sottosequenza ''A''[''i''..''n''];

# si scambia questo elemento con l'elemento ''i''-esimo.

|

[[File:Selection-Sort-Animation.gif|40px|border|left]]

|}

== Analisi delle prestazioni ==

* Si cerca il più piccolo elemento dell'array

Il ciclo interno è un semplice test per confrontare l'elemento corrente con il minimo elemento trovato fino a quel momento (più il codice per incrementare l'indice dell'elemento corrente e per verificare che esso non ecceda i limiti dell'array). Lo spostamento degli elementi è fuori dal ciclo interno: ogni scambio pone un elemento nella sua posizione finale quindi il numero di scambi è pari a <math> N-1</math> (dato che l'ultimo elemento non deve essere scambiato). Il tempo di calcolo è determinato dal numero di confronti.

* Scambia l'elemento più piccolo con l'elemento in prima posizione

* Incrementa l'indice e ricomincia il ciclo

A livello asintotico viene studiato il tempo di esecuzione dei due cicli for.

<math>\sum_{i=1}^{n-1} \sum_{j=i+1}^{n} c </math>, dove ''c'' è una costante, dato che l'operazione effettuata può essere rappresentata da una costante.

== Implementazioni ==

Seguono alcuni esempi di implementazione in vari [[linguaggi di programmazione|linguaggi]].

<math>\sum_{i=1}^{n-1} \sum_{j=i+1}^{n} 1 = \sum_{i=1}^{n-1} (n - (i + 1) + 1 ) = \sum_{i=1}^{n-1}(n-i) = \sum_{i=1}^{n-1} n - \sum_{i=1}^{n-1} i \approx n(n-1) - \frac{n(n - 1)}{2} \approx \frac{n^2}{2} = \theta(n^2) </math>

=== [[Linguaggio C|C]] ===

<nowiki>

void selection() {

int i, j, min, t;

L'ordinamento per selezione effettua <math>N(N-1)/2</math> confronti e, nel caso peggiore/migliore/medio, <math>\theta(n-1)</math> scambi.

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

min = i;

La complessità di tale algoritmo è dell'ordine di <math>\theta(n^2).</math>

for (j= i + 1; j <= N; j++)

if (a[j] < a[min]) min = j;

==Pseudocodice==

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

Quella che segue è una rappresentazione in [[pseudocodice]] del Selection sort:

}

}

</nowiki>

=== [[linguaggio Java|Java]] ===

<nowiki>

private static void scambio(Object a[], int ind1, int ind2 ){

Object tmp = a[ind1];

a[ind1] = a[ind2];

a[ind2] = tmp;

}

public static void selectionSort(Object a[]) {

for (int i=0; i<a.length-1; i++) {

int posMin = i;

for (int j=i+1; j<a.length; j++)

if (((Comparable)a[j]).compareTo(a[posMin])<0) posMin = j;

scambio(a,i,posMin);

}

}

</nowiki>

=== [[Linguaggio C|Pascal]] ===

<nowiki>

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.

</nowiki>

'''procedure''' SelectionSort(a: ''lista dei numeri da ordinare'');

== Analisi delle prestazioni ==

'''for''' i = 0 '''to''' n - 1

Il ciclo interno è un semplice test per confrontare l'elemento corrente con il minimo elemento trovato fino a quel momento (più il codice per incrementare l'indice dell'elemento corrente e per verificare che esso non ecceda i limiti dell'array). Lo spostamento degli elemento è fuori dal ciclo interno: ogni scambio pone un elemento nella sua posizione finale quindi il numero di scambi è pari a <math> N-1</math> (dato che l'ultimo elemento non deve essere scambiato). Il tempo di calcolo p determinato dal numero di confronti.

posmin ← i

'''for''' j = (i + 1) '''to''' n

'''if''' a[j] < a[posmin]

posmin ← j

'''if''' posmin != i

tmp ← a[i]

a[i] ← a[posmin]

a[posmin] ← tmp

==Implementazioni==

L'ordinamento per selezione effettua circa <math>N^2/2</math> confronti ed <math>N</math> scambi.

Di seguito una possibile implementazione in [[Java (linguaggio di programmazione)|Java]] :

<syntaxhighlight lang="java" line="1">

class SelectionSort{

public static void sort(int arr[]){

// Lunghezza array

int n=arr.length;

// Incrementa di 1 il limite inferiore del sub array da ordinare

for (int i = 0; i < n-1; i++)

{

// Trova il minimo nel subarray da ordinare

int indice_min = i;

for (int j = i+1; j < n; j++) {

// Confronto per trovare un nuovo minimo

if (arr[j] < arr[indice_min])

indice_min = j; // Salvo l'indice del nuovo minimo

}

// Scambia il minimo trovato con il primo elemento

swap(arr,indice_min,i);

}

}

private static void swap(int[] arr, int a , int b){

int temp = arr[a];

arr[a] = arr[b];

arr[b] = temp;

}

}

</syntaxhighlight>

== Casi limite ==

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

Un inconveniente dell'algoritmo di ordinamento per selezione è che il tempo di esecuzione dipende solo in modo modesto dal grado di ordinamento in cui si trova il file. La ricerca del minimo elemento durante una scansione del file non sembra dare informazioni circa la posizione del prossimo minimo nella scansione successiva. Chi utilizza questo algoritmo potrebbe stupirsi nel verificare che esso impiega più o meno lo stesso tempo sia su file già ordinati che su file con tutte le chiavi uguali, o anche su file ordinati in modo casuale.

Nonostante l'approccio ''brutale'' adottato, l'ordinamento per selezione ha un'importante applicazione: poiché ciascun elemento viene spostato al più una volta, questo tipo di ordinamento è il metodo da preferire quando si devono ordinare file costituiti da record estremamente grandi e da chiavi molto piccole. Per queste applicazioni il costo dello spostamento dei dati è prevalente sul costo dei confronti e nessun algoritmo è in grado di ordinare un file con spostamenti di dati sostanzialmente inferiori a quelli dell'ordinamento per selezione.

== CasiAltri limiteprogetti ==

{{interprogetto|b=Implementazioni di algoritmi/Selection sort|b_oggetto=implementazioni|b_preposizione=del|preposizione=sul}}

Un'inconveniente dell'algoritmo di ordinamento per selezione è che il tempo di esecuzione dipende solo in modo modesto dal grado di ordinamento in cui si trova il file. La ricerca del minimo elemento durante una scansione del file non sembra dere informazioni circa la posizione del prossimo minimo nella scansione successiva. Chi utilizza questo algoritmo potrebbe stupirsi nel verificare che esso impiega pià o meno lo stesso tempo sia su file già ordinati che su file con tutte le hiavi uguali, o anche su file ordinati in modo casuale.

== Collegamenti esterni ==

Nonostante l'approccio ''brutale'' adottato, ordinamento per selezione ha un'importante applicazione: poichè ciascun elemento viene spostato al pià una volta, questo tipo di ordinamento è il metodo da preferire quando si devono ordinare file costituiti da record estremamente grandi e da chiavi molto piccole. Per queste applicazioni il costo dello spostamento dei dati è prevalente sul costo dei confronti e nessun algoritmo è in grado di ordinare un file con spostamenti di dati sostanzialmente inferiori a quelli dell'ordinamento per selezione.

* {{Collegamenti esterni}}

{{ordinamento}}

{{portale|informatica}}

[[Categoria:Algoritmi di ordinamento]]