Selection sort: differenze tra le versioni

Versione delle 22:45, 1 set 2019

Versione attuale delle 09:42, 24 mar 2025

(23 versioni intermedie di 17 utenti non mostrate)

Riga 1:

{{Algoritmo

|classe = [[Algoritmo di ordinamento]]

|immagine = SelectionSorting selection sort animationanim.gif

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

|struttura dati = [[Array]]

Riga 10:

|ottimale = No

}}

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]]. L'algoritmo è di tipo non adattivo, ossia il suo tempo di esecuzione non dipende dall'input ma dalla dimensione dell'array.

== Descrizione dell'algoritmo ==

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.

{|

|

Riga 31 ⟶ 30:

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

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

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

Riga 40 ⟶ 39:

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

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

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

posmin ← i

Riga 54 ⟶ 53:

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

<sourcesyntaxhighlight 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++)

Riga 72:

// Scambia il minimo trovato con il primo elemento

swap(arr,indice_min,i);

}

}

Riga 83:

}

</syntaxhighlight>

</source>

== Casi limite ==

Riga 91:

== Altri progetti ==

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

== Collegamenti esterni ==

* {{Collegamenti esterni}}

{{ordinamento}}

{{portale|informatica}}

[[Categoria:Algoritmi di ordinamento]]