In questa lezione ci concentreremo sullo sviluppo dell’algoritmo di selection sort in linguaggio C, un metodo di ordinamento ampiamente utilizzato nella pratica della programmazione. Il selection sort è noto per la sua semplicità concettuale e la relativa facilità di implementazione, rendendolo un punto di partenza ideale per comprendere i concetti fondamentali degli algoritmi di ordinamento.
L’obiettivo principale del selection sort è quello di organizzare gli elementi di un array in ordine crescente (o decrescente). A differenza di alcuni altri algoritmi di ordinamento, come ad esempio il quicksort o il mergesort, il selection sort non si adatta all’input e il tempo di esecuzione dipende solo dalla dimensione dell’array. Questo lo rende non adattivo, ma allo stesso tempo lo rende relativamente prevedibile e facile da analizzare.
Il cuore del selection sort consiste nel selezionare ripetutamente l’elemento più piccolo dall’array e spostarlo nella posizione corretta nella parte già ordinata dell’array. Questo processo continua finché tutti gli elementi non sono stati inseriti nella sequenza ordinata. Quindi, a mano a mano che procediamo con l’algoritmo, otteniamo una sequenza ordinata che si estende da sinistra a destra.
Per implementare questo algoritmo in C, utilizziamo due indici: i, che scorre dall’inizio dell’array fino a N − 2, e j, che parte da i + 1 e va fino a N − 1, dove N è la dimensione dell’array. Iteriamo attraverso l’array e, ad ogni passaggio, troviamo l’indice dell’elemento più piccolo nella parte non ordinata dell’array. Successivamente, scambiamo questo elemento con l’elemento nella posizione corrente i. Questo processo continua fino a quando non abbiamo inserito tutti gli elementi nella sequenza ordinata.
Una parte cruciale dell’algoritmo è la necessità di una variabile temporanea t per consentire lo scambio tra gli elementi. Quando troviamo l’elemento più piccolo, lo scambiamo con l’elemento alla posizione i utilizzando questa variabile temporanea.
Ecco dunque come utilizziamo la variabile temporanea:
t = a[min];
a[min] = a[i];
a[i] = t;
Dove la variabile t è dunque una 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;
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];
a[min] = a[i];
a[i] = t;
}
for(i = 0; i < 10; i++) {
printf("%d ", a[i]);
}
}
Prestazioni del selection sort
L’algoritmo selection sort effettua N(N−1)/2 confronti, quindi la sua complessità è dell’ordine di θ(n2).
Sebbene questa complessità possa renderlo meno efficiente rispetto ad altri algoritmi come il mergesort o il quicksort, la sua semplicità lo rende una scelta ragionevole per piccoli insiemi di dati o quando la facilità di implementazione è una priorità.
Conclusioni
In questa lezione abbiamo implementato l’algoritmo di selection sort in linguaggio C, comprendendo i suoi principi fondamentali e la sua implementazione pratica. Nelle future lezioni, esamineremo ulteriori algoritmi di ordinamento e approfondiremo le loro applicazioni e prestazioni.
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);
....
In questa lezione imparare a popolare un array con numeri random in C.
Nella programmazione, spesso è necessario generare numeri casuali e caricarli in un array per scopi vari, come la simulazione di dati o la generazione di input per algoritmi di test. In questo articolo, vedremo come caricare un array con numeri casuali in C, utilizzando la libreria standard <stdio.h> e <time.h>.
Procedura per popolare un array con numeri random in C
La procedura che ho adottato prevede i seguenti passaggi:
Inizializzazione del Generatore di Numeri Casuali: Utilizziamo la funzione srand(time(0)) per inizializzare il generatore di numeri casuali sull’ora attuale dell’elaboratore. Questo assicura che ogni volta che il programma viene eseguito, verranno generati numeri casuali diversi.
Generazione dei Numeri Casuali e Caricamento nell’Array: Utilizziamo un ciclo for per iterare su tutte le posizioni dell’array e generare numeri casuali compresi tra 1 e 100 utilizzando l’espressione 1 + rand() % 100. I numeri generati vengono quindi caricati nell’array.
Visualizzazione dei Numeri Casuali Generati: Utilizziamo un altro ciclo for per visualizzare i numeri casuali generati e caricati nell’array.
Ecco dunque il codice completo:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 20
int main() {
int a[N];
int i;
// Inizializzazione del generatore di numeri casuali sull'ora attuale
srand(time(0));
// Generazione dei numeri casuali e caricamento nell'array
for (i = 0; i < N; i++) {
a[i] = 1 + rand() % 100; // Numeri casuali tra 1 e 100
}
// Visualizzazione dei numeri casuali generati
printf("Numeri casuali generati:\n");
for (i = 0; i < N; i++) {
printf("%d\t", a[i]);
}
printf("\n");
return 0;
}
In questo esempio, abbiamo utilizzato la funzione rand() per generare numeri casuali e la funzione srand(time(0)) per inizializzare il generatore di numeri casuali sull’ora attuale dell’elaboratore. Abbiamo quindi caricato i numeri casuali generati nell’array a e li abbiamo visualizzati tramite un ciclo for.
Conclusioni
In questa lezione abbiamo visto un semplice esempio di come generare un array con numeri random in C, nella prossima lezione impareremo a generare dei numeri casuali senza ripetizioni.
Commenti recenti