Selection sort: differenze tra le versioni

Versione delle 07:14, 1 giu 2019

Versione attuale delle 09:42, 24 mar 2025

(25 versioni intermedie di 18 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[]){

int// szLunghezza = arr.length;array

int n=arr.length;

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

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

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

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

// Trova il minimo if(arr[i]nel > arr[j]) swap(arr,i,j); //subarray ordineda ascendenteordinare

int indice_min = i;

for (int ij =0; i<sz-+1;i 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[] arr, int posaa , int posbb){

int tmptemp = arr[posaa];

arr[posaa] = arr[posbb];

arr[posbb] = tmptemp;

}

}

</syntaxhighlight>

</source>

== Casi limite ==

Riga 83 ⟶ 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]]