Selection sort: differenze tra le versioni

Versione delle 17:11, 2 dic 2007

Versione attuale delle 09:42, 24 mar 2025

(160 versioni intermedie di 99 utenti non mostrate)

Riga 1:

{{Algoritmo

L<nowiki>'</nowiki>'''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]]; seleziona 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.

|classe = [[Algoritmo di ordinamento]]

L'algoritmo è di tipo non adattivo, ossia il suo tempo di esecuzione non dipende dall'input ma dalla dimensione dell'array.

|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 inizializza un puntatore ''i'' che va da 1 a n (dove n è la lunghezza 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.

* Si cerca il più piccolo elemento dell'array

* Scambia l'elemento più piccolo con l'elemento alla posizione ''i''

* Incrementa l'indice ''i'' e si torna al passo uno fino alla fine dell'array.

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>

=== [[C (linguaggio)|C]] ===

<source lang="C">

void selection(double a[], unsigned long N) {

int i, j, min;

double 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;

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

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

min = j;

t = a[min];

a[min] = a[i];

a[i] = t;

}

}

</source>

<!--

====Implementazione Alternativa====

<nowiki>

void selection(double a[], unsigned long N) {

int i, j;

double t;

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

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

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

if(a[i] > a[j]) {

t = a[j];

a[j] = a[i];

a[i] = t;

}

}

}

}

</nowiki> -->

==Pseudocodice==

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

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

<source lang="Java">

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

Object tmp = a[ind1];

a[ind1] = a[ind2];

a[ind2] = tmp;

}

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

public static void selectionSort(Object a[]) {

'''for''' (inti i= 0; i'''to''' <n a.length- 1; i++) {

posmin int posMin =← i;

'''for (int''' j = (i + 1;) j < a.length; j++)'''to''' {n

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

} posmin ← j

'''if''' posmin != i

scambio(a,i,posMin);

tmp ← a[i]

}

a[i] ← a[posmin]

}

a[posmin] ← tmp

</source>

==Implementazioni==

=== [[Pascal (linguaggio)|Pascal]] ===

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

<source lang="Pascal">

const dim=20;

procedure SelectionSort(var a: array[1..dim] of integer);

var

n,i,j,pos,min,aus:integer;

begin

for i:=1 to n-1 do

begin

pos:= i;

for j:=(i+1) to n do

if a[j]< a[pos] then

pos:= j;

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

aus:= a[i];

class SelectionSort{

a[i]:= a[pos];

a[pos]:= aus;

public static void sort(int arr[]){

end;

// Lunghezza array

end;

int n=arr.length;

</source>

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

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

===[[PHP]]===

{

<source lang="PHP">

// Trova il minimo nel subarray da ordinare

function selection_sort(&$a) {

int indice_min = i;

for ($iint j = i+1; $ij < count($a)-1n; $ij++) {

$min_index = $j;

// Confronto per trovare un nuovo minimo

for($j = $i + 1; $j < count($a); $j++)

if ($aarr[$j] < $aarr[$iindice_min])

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

$min_index = $j;

}

$transfer = $a[$min_index];

$array[$min_index] = $a[$i];

// Scambia il minimo trovato con il primo elemento

$array[$i] = $transfer;

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>

</source>

== AnalisiCasi delle prestazionilimite ==

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.

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.

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.

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

== Altri progetti ==

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

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

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

== Collegamenti esterni ==

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

* {{Collegamenti esterni}}

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

== Casi limite ==

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, 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.

{{ordinamento}}

{{portale|informatica}}

[[Categoria:Algoritmi di ordinamento]]

[[cs:Selection sort]]

[[da:Udtagelsessortering]]

[[de:Selectionsort]]

[[en:Selection sort]]

[[es:Ordenamiento por selección]]

[[fr:Tri par sélection]]

[[he:מיון בחירה]]

[[ja:選択ソート]]

[[ko:선택 정렬]]

[[lt:Išrinkimo rikiavimo algoritmas]]

[[pl:Sortowanie przez wybieranie]]

[[pt:Selection sort]]

[[ru:Сортировка выбором]]

[[vi:Sắp xếp chọn]]

[[zh:选择排序]]