Selection sort in C

Oggi ci occuperemo dello sviluppo dell’algoritmo selection sort in C.

Il selection sort è un algoritmo di ordinamento.

Il suo tempo di esecuzione non dipende dall’input bensì dalla dimensione dell’array, dunque si dice che è non adattivo.
L’algoritmo di volta in volta seleziona il numero minore della sequenza e lo sposta nella sequenza ordinata.
Di fatto a mano a mano avremo una sequenza ordinata a partire da sinistra.

Per realizzare questo algoritmo si considera allora l’indice i che va dalla posizione 0 dell’array fino ad arrivare a N-2 (consideriamo un vettore di dimensione N) e un’altro indice j che va da i+1 fino ad arrivare a N-1.
Quindi si trova l’elemento più piccolo dell’array e si scambia con l’elemento alla posizione i, dopo incrementa l’indice di uno e si ritorna al passo precedente.

Servirà una variabile per poter effettuare lo scambio.

Difatti quando si trova l’elemento più piccolo dell’array si scambia con l’elemento alla posizione i:

t = a[min];

a[min] = a[i];

a[i] = t;

Esempio di algoritmo selection sort in C:

#include <stdio.h>
//algoritmo di ordinamento selection sort in linguaggio C

main()
{
	int a[10]={5,8,0,1,4,2,4,3,9,7};
	int i,j,min,t; 
//t è la variabile temporanea utilizzata per lo scambio for(i=0; i<9; i++){ min=i; for (j=i+1;j<10;j++){ if (a[j]<a[min]) min=j; } t = a[min];
// si trova l'elemento più piccolo dell'array e si scambia con l'elemento alla posizione i a[min] = a[i]; a[i] = t; printf("%d ", a[i]); } }

Prestazioni del selection sort

Vediamo adesso le prestazioni del selection sort.

L’ordinamento per selezione effettua N ( N − 1 ) / 2 confronti, la complessità di tale algoritmo è dell’ordine di θ (n2). 

L’algoritmo in effetti risulta poco efficiente, per la sua complessità esponenziale, ma è piuttosto facile da implementare. 

Alcuni link utili dove trovare altri algoritmi sviluppati in linguaggio C

Array o vettori

Quick sort in linguaggio C

Merge sort in linguaggio C

Insertion Sort in lingaggio C

Autore dell'articolo: cristina

Avatar per Coding Creativo

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *