Oggi ci occuperemo dello sviluppo dell’algoritmo selection sort in C.
Il selection sort è un algoritmo di ordinamento che in questo blog affronteremo con vari linguaggi di programmazione, ma in questo articolo lo svilupperemo in linguaggio C.
Il tempo di esecuzione di questo algoritmo di ordinamento 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 l’algoritmo selection sort in C 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à quindi 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;
La variabile t dunque rappresenta la variabile temporanea.
Esempio di algoritmo selection sort in C
Vediamo adesso il codice completo dell’algoritmo di ordinamento in linguaggio C:
#include <stdio.h>
int 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;
}
for(i=0; i<10; i++){
printf("%d ", a[i]);
}
}
Prestazioni del selection sort
Vediamo adesso le prestazioni dell’algoritmo selection sort.
L’ordinamento per selezione effettua N ( N − 1 ) / 2 confronti, dunque 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.
Conclusioni
In questa lezione abbiamo affrontato l’algoritmo di ordinamento selection sort in C, nella prossima lezione affronteremo anche altri algoritmi di ordinamento.
Realizziamo un programma in C che, data una matrice quadrata di ordine N, determini la somma degli elementi della diagonale principale di una matrice.
Definizione di diagonale principale di una matrice
La diagonaleprincipale di una matricequadrata è la diagonale che va dall’angolo in alto a sinistra a quello in basso a destra.
La diagonale secondaria di una matrice quadrata è la diagonale che va dall’angolo in alto a destra a quello in basso a sinistra.
Nella figura sotto ho evidenziato in rosso la diagonale principale e in verde quella secondaria.
Procedimento
Vogliamo dunque costruire un algoritmo che, data una matrice quadrata di ordine N, determini la somma degli elementi della diagonale principale di una matrice.
Innanzitutto prendiamo in input una matrice quadrata di ordine N, inseriamo i dati nella matrice e facciamo queste considerazioni.
La diagonale principale di una matrice 3 x 3 è data dagli elementi a(0,0) , a(1,1) e a(2,2).
Mentre la diagonale principale di una matrice 4 x 4 è data dagli elementi a(0,0) , a(1,1) , a(2,2) e a(3,3). E così via.
Quindi la diagonale principale di una matrice è data dagli elementi il cui indice j è uguale all’indice i.
Pertanto per ottenere la somma, basta semplicemente fare:
for(i=0;i<n;i++)
somma_d += a[i][i];
/*somma_d è la variabile che contiene la somma degli elementi con indice j=i.*/
Allo stesso modo ragioniamo per la diagonale secondaria.
Gli elementi della diagonale secondaria di una matrice 3 x 3 sono a(0,2) , a(1,1) e a(2,0).
Mentre se la matrice è 4 x 4 gli elementi della diagonale secondaria sono a(0,3) , a(1,2) , a(2,1) e a(3,0).
Notiamo, nel caso della matrice 3×3, che l’indice i parte da 0 e arriva a 2 mentre l’indice j parte da 2 e arriva a 0, cioè l’indice i si incrementa mentre l’indice j si decrementa. Così anche nella matrice 4 x4, ecc…
Dunque per queste considerazioni avremo:
for(i=0,j=n-1;i<n;i++,j--)
somma_s += a[i][j];
/*somma_s è la variabile che contiene la somma degli elementi della diagonale secondaria*/
Allego tutto il listato
#include<stdio.h>
#define N 100
int main(){
int a[N][N],n,m,i,j,somma_d=0,somma_s=0;
do {
printf("Dammi il numero di righe e colonne: ");
scanf("%d", &n);
} while ((n>N) || (N<1));
printf("\nInseriamo i dati nella matrice \n");
for (i=0;i<n;i++)
for (j=0;j<n;j++) {
printf("Inserisci elemento di riga %d e colonna %d: ", i, j);
scanf("%d", &a[i][j]);
}
printf("\nStampiamo i dati \n");
for (i=0;i<n;i++) {
printf("\n");
for(j=0;j<n;j++)
printf("\t%d", a[i][j]);
}
for(i=0;i<n;i++)
somma_d += a[i][i]; //somma diagonale principale
for(i=0,j=n-1;i<n;i++,j--)
somma_s += a[i][j];*/ //somma diagonale secondaria
printf("la somma della diagonale principale e' %d\n",somma_d);
printf("la somma della diagonale secondaria e' %d\n",somma_s);
}
Esempio di calcolo della somma degli elementi che si trovano sopra la diagonale principale.
Adesso ci poniamo il problema di voler calcolare la somma degli elementi che si trovano sopra la diagonale principale, in definitiva gli elementi della sotto-matrice triangolare superiore.
Quindi facciamo nuovamente le nostre considerazioni.
Nel caso di una matrice 3 x 3, gli elementi che si trovano al di sopra la diagonale principale sono a(0,1) , a(0,2) e a(1,2).
Nel caso di una matrice 4 x 4, gli elementi che si trovano al di sopra la diagonale principale sono a(0,1) , a(0,2) , a(0,3) , a(1,2) , a(1,3) e a(2,3).
Uno dei modi per ottenere ciò è usare due cicli.
//somma elementi al di sopra della diagonale principale
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
somma+=a[i][j];
Analogamente per sommare gli elementi al di sotto della diagonale principale, ovvero gli elementi della sotto-matrice triangolare inferiore.
//somma elementi al di sotto della diagonale principale
for(j=0;j<n;j++)
for(i=j+1;i<n;i++)
somma2+=a[i][j];
Dunque, allego il listato completo:
#include<stdio.h>
#define N 100
int main(){
int a[N][N],n,m,i,j,somma=0,somma2=0, somma_d=0, somma_s=0;
do {
printf("Dammi il numero di righe e colonne: ");
scanf("%d", &n);
} while ((n>N) || (N<1));
printf("\nInseriamo i dati nella matrice \n");
for (i=0;i<n;i++)
for (j=0;j<n;j++) {
printf("Inserisci elemento di riga %d e colonna %d: ", i, j);
scanf("%d", &a[i][j]);
}
printf("\nStampiamo i dati \n");
for (i=0;i<n;i++) {
printf("\n");
for(j=0;j<n;j++)
printf("\t%d",a[i][j]);
}
for(i=0;i<n;i++)
somma_d += a[i][i]; //somma diagonale principale
for(i=0,j=n-1;i<n;i++,j--)
somma_s += a[i][j]; //somma diagonale secondaria
//somma elementi al di sopra della diagonale principale
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
somma+=a[i][j];
//somma elementi al di sotto della diagonale principale
for(j=0;j<n;j++)
for(i=j+1;i<n;i++)
somma2+=a[i][j];
printf("\nla somma della diagonale principale e' %d\n",somma_d);
printf("la somma della diagonale secondaria e' %d\n",somma_s);
printf("la somma degli elementi sopra diagonale principale e' %d\n",somma);
printf("la somma degli elementi sotto diagonale principale e' %d\n",somma2);
}
Se ad esempio volessimo ottenere la somma degli elementi della diagonale che sta sotto quella principale, allora basterebbe sommare gli elementi di posto a[i+1][i].
for(i=0;i<n-1;i++)
somma_d1 += a[i+1][i];
Questi sono solo degli esempi di possibili soluzioni agli esercizi proposti. Proponete pure le vostre nei commenti sotto.
Realizziamo un algoritmo per il calcolo della somma degli elementi appartenenti alla cornice esterna di una matrice in C.
Consideriamo una matrice a[M][N] e definiamo in 100 il numero massimo di righe e di colonne.
Al solito chiediamo di inserire il numero di righe e di colonne della matrice e controlliamo che il valore inserito non sia maggiore di 100 e non sia minore di 1.
Dopo iniziamo ad inserire gli elementi nella matrice utilizzando due cicli, uno più esterno che scandisce mediante la variabile i le righe e un altro più interno che percorre per mezzo della variabile j le colonne.
Per calcolare la somma degli elementi della cornice esterna della matrice, basta fare questa considerazione:
Gli elementi della cornice esterna saranno quelli dove:
i è uguale a 0 oppure i è uguale a m-1 e j è uguale a 0 oppure j è uguale a n-1
Quindi facciamo un semplice controllo e se la condizione è vera allora facciamo la somma degli elementi appartenenti alla cornice esterna:
if(i==0 || j==0 || i == m-1 || j==n-1) somma += a[i][j];
Listato completo dell’algoritmo per il calcolo della somma degli elementi appartenenti alla cornice esterna di una matrice in C
#include<stdio.h>
#define N 100
#define M 100
int main(){
int a[M][N],n,m,i,j,somma=0;
do {
printf("Dammi il numero di righe: ");
scanf("%d", &m);
} while ((m>M) || (m<1));
do {
printf("Dammi il numero di colonne: ");
scanf("%d", &n);
} while ((n>N)|| (n<1));
printf("\nInseriamo i dati nella matrice \n");
for (i=0;i<m;i++)
for(j=0;j<n;j++) {
printf("Inserisci elemento di riga %d e colonna %d: ", i, j);
scanf("%d", &a[i][j]);
}
printf("\nStampiamo i dati \n");
for (i=0;i<m;i++) {
printf("\n");
for(j=0;j<n;j++)
printf("\t%d", a[i][j]);
}
for(i=0;i<m;i++)
for(j=0;j<n;j++)
if(i==0 || j==0 || i == m-1 || j==n-1)
somma += a[i][j];
printf("\nsomma = %d",somma);
}
Se volessimo fare la somma degli elementi interni, esclusa la cornice allora basterà creare un’altra variabile:
int somma_i=0, somma_e=0;
.....
for(i=0;i<m;i++)
for(j=0;j<n;j++)
if(i==0 || j==0 || i == m-1 || j==n-1)
somma_e += a[i][j];
else somma_i+= a[i][j];
printf("\nsomma cornice = %d\n",somma_e);
printf("\nsomma elementi interni= %d\n",somma_i);
....
È possibile caricare un array con numeri random in C, ovvero con dei numeri a caso tra un intervallo di valori.
Ecco un esempio che carica in modo random, con numeri da 1 a 100, un array di 20 numeri.
A questo scopo, viene utilizzata l’istruzione srand(time(0)) che serve a inizializzare il generatore sull’ora attuale dell’elaboratore.
Questo infatti garantisce che ogni volta si ottengano valori diversi. La funzione 1+rand()%100; crea numeri casuali tra 1 e 100.
Quindi con un semplice ciclo for che scandisce tutte le posizioni dell’array vado ad inserire gli elementi nelle varie posizioni.
Ecco dunque il listato completo:
#include
#include
#define N 20
main(){
int a[N];
int i;
/*inizializzamo il generatore sull'ora attuale
dell'elaboratore time(0), in questo modo si hanno
valori diversi*/
srand(time(0));
for(i = 0; i < N; i++){
a[i]=1+rand()%100; //numeri casuali tra 1 e 100
printf("%d\t", a[i]);
}
}
```c
#include <stdio.h>
#include <time.h>
#define N 20
main(){
int a[N];
int i;
/*inizializzamo il generatore sull'ora attuale
dell'elaboratore time(0), in questo modo si hanno
valori diversi*/
srand(time(0));
for(i=0;i<N;i++){
a[i]=1+rand()%100; //numeri casuali tra 1 e 100
printf("%d\t", a[i]);
}
}
```
Chiaramente questo è solo un semplice esempio di come generare un array con numeri random in C, nella prossima lezione impareremo a generare dei numeri casuali senza ripetizioni.
