Selection sort: differenze tra le versioni

Versione delle 13:23, 27 mar 2020

Versione attuale delle 09:42, 24 mar 2025

(22 versioni intermedie di 16 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 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]]