ALGORITMI ALGORITMI DI DI

ORDINAMENTOORDINAMENTO

SELECTIONSELECTIONSORTSORT

• Algoritmo intuitivo ed estremamente semplice.• Utile quando l’insieme da ordinare è composto da

pochi elementi.

Idea di fondo ripetere per n volte una procedura in grado di selezionare alla i-esima iterazione l’elemento più piccolo nell’insieme e di scambiarlo con l’elemento che in quel momento occupa la posizione i.

1. Alla prima iterazione dell’algoritmo verrà selezionato l’elemento più piccolo dell’intero insieme e sarà scambiato con quello che occupa la prima posizione;

2. Alla seconda iterazione sarà selezionato il secondo elemento più piccolo dell’insieme (ossia l’elemento più piccolo dell’insieme “ridotto” costituito dagli elementi {a2, a3, . . . , an} e sarà scambiato con l’elemento che occupa la seconda posizione, e così via fino ad aver collocato nella posizione corretta tutti gli n elementi.

SELECTIONSORTSELECTIONSORT

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: 1.la sottosequenza ordinata, che occupa le prime posizioni dell'array, 2.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.

SELECTIONSORTSELECTIONSORT

Di seguito un esempio di questo algoritmo di ordinamento con dieci elementi:

SELECTIONSORTSELECTIONSORT

PSEUDOCODICE

i = 1posmin = 1j = 2

i

jj = 9posmin 9a[i] = 8a[posmin] = 0

a[i] a[posmin]

.

.

.

SELECTIONSSELECTIONSORTORT

#include <stdio.h>#include <stdlib.h> int main(){ int a[100], n, i, j, posmin, aus; /* * Legge in input il numero n ed n numeri * interi che memorizza nell'array. */ printf(“Inserisci il numero di elementi\n”); scanf(“%d”, &n); printf(“Inserisci %d numeri interi\n”, n); for ( i = 0 ; i < n ; i++ ) scanf(“%d”, &a[i]); /* * Ordina l’array. Se posmin=i vuol dire che * l’elemento si trova al posto giusto, * ovvero a[i] è il valore minimo e non è * necessario effettuare lo scambio. */  for ( i = 0 ; i < ( n - 1 ) ; i++ ) { posmin = i; for ( j = i + 1 ; j < n ; j++ ) { if ( a[j] < a[posmin] ) posmin = j; } if ( posmin != i ) { aus = a[i]; a[i] = a[posmin]; a[posmin] = aus; } }

/* * Restituisce l’array ordinato. */  printf(“Lista ordinata in ordine crescente:\n”); for ( i = 0 ; i < n ; i++ ) printf(“%d\n”, array[i]); system(“pause”); return 0;}

PSEUDOCODICE

SELECTIONSORT IN CSELECTIONSORT IN C