Lezione 6 · Array e ordinamento · Corso C++

Definizione

Cos'è un array

Un array è una struttura dati omogenea: contiene molti dati, tutti dello stesso tipo, raccolti sotto un unico nome. Si divide in due famiglie: i vettori (a una dimensione) e le matrici (a due dimensioni).

1 dimensione

I vettori

Un vettore è monodimensionale: una sola riga di N celle (dimensione 1 × N). Ogni cella è individuata da un indice, una variabile che ne rappresenta la posizione. Gli indici vanno da 0 a N−1.

Il vettore v: ogni cella ha un indice, si parte da 0.

vettore.cpp

const int N = 5;
int v[N];                         // 5 celle: v[0]..v[4]
for (int i = 0; i < N; i++) cin >> v[i];   // riempimento
for (int i = 0; i < N; i++) cout << v[i];  // lettura

2 dimensioni

Le matrici

Una matrice è bidimensionale: una tabella di N righe e M colonne (dimensione N × M). Ogni cella è individuata da due indici: i per la riga (0 ≤ i ≤ N−1) e j per la colonna (0 ≤ j ≤ M−1).

La cella m[2][1]: riga 2 (i), colonna 1 (j).

matrice.cpp

const int R = 3, C = 4;
int m[R][C];
for (int i = 0; i < R; i++)         // righe
    for (int j = 0; j < C; j++)     // colonne
        cin >> m[i][j];

Algoritmi

L'ordinamento

Un'operazione fondamentale sui vettori è ordinare gli elementi. Gli algoritmi più semplici da capire sono il bubble sort e il selection sort: confrontano coppie di elementi e li scambiano quando sono nell'ordine sbagliato.

Bubble sort: a ogni passo i valori più grandi "salgono" verso il fondo come bolle.

bubblesort.cpp

void bubbleSort(int v[], const int N) {
    for (int i = 0; i < N - 1; i++)
        for (int j = 0; j < N - 1 - i; j++)
            if (v[j] > v[j + 1]) {       // fuori ordine: scambia
                int t = v[j]; v[j] = v[j + 1]; v[j + 1] = t;
            }
}

Esercizi

Gli esercizi

Sei gruppi di esercizi: vettori, matrici e algoritmi di ordinamento, ognuno in versione base e avanzata.

Vettori

Vettori — basescarica ↓

Vettori — avanzatiscarica ↓

Soluzioni · Vettori base

1 — Leggi e stampa
void leggiVettore(int v[], const int N){ for(int i=0;i<N;i++) cin>>v[i]; }
void stampaVettore(int v[], const int N){ for(int i=0;i<N;i++) cout<<v[i]<<" "; }

2 — Statistiche
float somma(float v[], const int N){ float s=0; for(int i=0;i<N;i++) s+=v[i]; return s; }
float media(float v[], const int N){ return somma(v,N)/N; }
float massimo(float v[], const int N){ float m=v[0]; for(int i=1;i<N;i++) if(v[i]>m) m=v[i]; return m; }
float minimo(float v[], const int N){ float m=v[0]; for(int i=1;i<N;i++) if(v[i]<m) m=v[i]; return m; }

3 — Occorrenze
int contaOccorrenze(int v[], const int N, int val){
    int c=0; for(int i=0;i<N;i++) if(v[i]==val) c++; return c; }

4 — Conta dispari
int contaDispari(int v[], const int N){
    int c=0; for(int i=0;i<N;i++) if(v[i]%2!=0) c++; return c; }

5 — Ricerca lineare
int cerca(int v[], const int N, int val){
    for(int i=0;i<N;i++) if(v[i]==val) return i;
    return -1; }

6 — Inverti
void inverti(int v[], const int N){
    for(int i=0;i<N/2;i++){ int t=v[i]; v[i]=v[N-1-i]; v[N-1-i]=t; } }

7 — Somma di due vettori
void sommaVettori(int a[], int b[], int r[], const int N){
    for(int i=0;i<N;i++) r[i]=a[i]+b[i]; }

8 — Minimo e posizione
int indiceMinimo(int v[], const int N){
    int p=0; for(int i=1;i<N;i++) if(v[i]<v[p]) p=i; return p; }

9 — Sopra la media
int contaSopraMedia(float v[], const int N){
    float m=media(v,N); int c=0;
    for(int i=0;i<N;i++) if(v[i]>m) c++; return c; }

10 — Copia
void copia(int o[], int d[], const int N){
    for(int i=0;i<N;i++) d[i]=o[i]; }

Soluzioni · Vettori avanzati

1 — Ordina (selection sort)
void ordina(int v[], const int N){
    for(int i=0;i<N-1;i++){
        int mn=i;
        for(int j=i+1;j<N;j++) if(v[j]<v[mn]) mn=j;
        int t=v[i]; v[i]=v[mn]; v[mn]=t;
    } }

2 — Ricerca binaria // vettore ordinato
int ricercaBinaria(int v[], const int N, int val){
    int lo=0, hi=N-1;
    while(lo<=hi){
        int mid=(lo+hi)/2;
        if(v[mid]==val) return mid;
        if(v[mid]<val) lo=mid+1; else hi=mid-1;
    } return -1; }

3 — Valori distinti
int contaDistinti(int v[], const int N){
    int c=0;
    for(int i=0;i<N;i++){
        bool nuovo=true;
        for(int j=0;j<i;j++) if(v[j]==v[i]) nuovo=false;
        if(nuovo) c++;
    } return c; }

9 — Secondo massimo
int secondoMassimo(int v[], const int N){
    int m1=v[0], m2=-2147483647;
    for(int i=1;i<N;i++){
        if(v[i]>m1){ m2=m1; m1=v[i]; }
        else if(v[i]>m2 && v[i]<m1) m2=v[i];
    } return m2; }

Gli esercizi 4–8 e 10 (rimozione duplicati, inserimento ordinato, rotazione, fusione, prodotto scalare, vettore palindromo) seguono gli stessi schemi.

Matrici

Matrici — basescarica ↓

Matrici — avanzatiscarica ↓

Soluzioni · Matrici base

1 — Stampa // const int R, C globali
void stampaMatrice(int m[][C]){
    for(int i=0;i<R;i++){
        for(int j=0;j<C;j++) cout<<m[i][j]<<"\t";
        cout<<endl;
    } }

2 — Somma totale
int sommaTotale(int m[][C]){
    int s=0;
    for(int i=0;i<R;i++) for(int j=0;j<C;j++) s+=m[i][j];
    return s; }

3 — Somma per riga
int sommaRiga(int m[][C], int riga){
    int s=0; for(int j=0;j<C;j++) s+=m[riga][j]; return s; }

4 — Somma per colonna
int sommaColonna(int m[][C], int col){
    int s=0; for(int i=0;i<R;i++) s+=m[i][col]; return s; }

5 — Massimo
int massimo(int m[][C]){
    int mx=m[0][0];
    for(int i=0;i<R;i++) for(int j=0;j<C;j++) if(m[i][j]>mx) mx=m[i][j];
    return mx; }

6 — Conta pari
int contaPari(int m[][C]){
    int c=0;
    for(int i=0;i<R;i++) for(int j=0;j<C;j++) if(m[i][j]%2==0) c++;
    return c; }

7 — Somma di due matrici
void sommaMatrici(int a[][C], int b[][C], int r[][C]){
    for(int i=0;i<R;i++) for(int j=0;j<C;j++) r[i][j]=a[i][j]+b[i][j]; }

8 — Diagonale principale
void stampaDiagonale(int m[][C]){
    for(int i=0;i<R;i++) cout<<m[i][i]<<" "; }

9 — Traccia
int traccia(int m[][C]){
    int s=0; for(int i=0;i<R;i++) s+=m[i][i]; return s; }

10 — Cerca
bool cerca(int m[][C], int val, int &riga, int &col){
    for(int i=0;i<R;i++) for(int j=0;j<C;j++)
        if(m[i][j]==val){ riga=i; col=j; return true; }
    return false; }

Soluzioni · Matrici avanzati

1 — Trasposta // const int N globale
void trasposta(int m[][N], int t[][N]){
    for(int i=0;i<N;i++) for(int j=0;j<N;j++) t[j][i]=m[i][j]; }

3 — Simmetrica
bool eSimmetrica(int m[][N]){
    for(int i=0;i<N;i++) for(int j=0;j<N;j++)
        if(m[i][j]!=m[j][i]) return false;
    return true; }

5 — Somma delle diagonali
int diagPrincipale(int m[][N]){ int s=0; for(int i=0;i<N;i++) s+=m[i][i]; return s; }
int diagSecondaria(int m[][N]){ int s=0; for(int i=0;i<N;i++) s+=m[i][N-1-i]; return s; }

7 — Scambia due righe
void scambiaRighe(int m[][N], int r1, int r2){
    for(int j=0;j<N;j++){ int t=m[r1][j]; m[r1][j]=m[r2][j]; m[r2][j]=t; } }

Gli esercizi 2, 4, 6, 8–10 (prodotto righe×colonne, identità, massimo per riga, triangolare, cornice, righe sopra soglia) seguono gli stessi schemi di scansione a doppio indice.

Ordinamento

Ordinamento — basescarica ↓

Ordinamento — avanzatiscarica ↓

Soluzioni · Ordinamento base

1 — Bubble sort crescente
void bubbleSort(int v[], const int N){
    for(int i=0;i<N-1;i++) for(int j=0;j<N-1-i;j++)
        if(v[j]>v[j+1]){ int t=v[j]; v[j]=v[j+1]; v[j+1]=t; } }

2 — Bubble sort decrescente
void bubbleSortDesc(int v[], const int N){
    for(int i=0;i<N-1;i++) for(int j=0;j<N-1-i;j++)
        if(v[j]<v[j+1]){ int t=v[j]; v[j]=v[j+1]; v[j+1]=t; } }

3 — Selection sort
void selectionSort(int v[], const int N){
    for(int i=0;i<N-1;i++){
        int mn=i;
        for(int j=i+1;j<N;j++) if(v[j]<v[mn]) mn=j;
        int t=v[i]; v[i]=v[mn]; v[mn]=t;
    } }

4 — Porta in testa il minimo
void minimoInTesta(int v[], const int N){
    int mn=0;
    for(int i=1;i<N;i++) if(v[i]<v[mn]) mn=i;
    int t=v[0]; v[0]=v[mn]; v[mn]=t; }

5 — Conta gli scambi
int bubbleSortConteggio(int v[], const int N){
    int sc=0;
    for(int i=0;i<N-1;i++) for(int j=0;j<N-1-i;j++)
        if(v[j]>v[j+1]){ int t=v[j]; v[j]=v[j+1]; v[j+1]=t; sc++; }
    return sc; }

6 — Gia' ordinato?
bool eOrdinato(int v[], const int N){
    for(int i=0;i<N-1;i++) if(v[i]>v[i+1]) return false;
    return true; }

7 — Mediana
int mediana(int v[], const int N){ ordina(v,N); return v[N/2]; }

8 — Podio
void stampaPodio(int v[], const int N){
    ordinaDesc(v,N);
    for(int i=0;i<3 && i<N;i++) cout<<(i+1)<<"o: "<<v[i]<<endl; }

9 — Ordina caratteri
void ordinaCaratteri(char v[], const int N){
    for(int i=0;i<N-1;i++) for(int j=0;j<N-1-i;j++)
        if(v[j]>v[j+1]){ char t=v[j]; v[j]=v[j+1]; v[j+1]=t; } }

10 — Senza duplicati
void stampaSenzaDuplicati(int v[], const int N){
    ordina(v,N);
    for(int i=0;i<N;i++) if(i==0 || v[i]!=v[i-1]) cout<<v[i]<<" "; }

Soluzioni · Ordinamento avanzati

1 — Insertion sort
void insertionSort(int v[], const int N){
    for(int i=1;i<N;i++){
        int x=v[i], j=i-1;
        while(j>=0 && v[j]>x){ v[j+1]=v[j]; j--; }
        v[j+1]=x;
    } }

5 — Ordina struct per media
struct Studente { string nome; float media; };
void ordinaPerMedia(Studente s[], const int N){
    for(int i=0;i<N-1;i++) for(int j=0;j<N-1-i;j++)
        if(s[j].media<s[j+1].media){ Studente t=s[j]; s[j]=s[j+1]; s[j+1]=t; } }

9 — Ordina stringhe
void ordinaStringhe(string v[], const int N){
    for(int i=0;i<N-1;i++) for(int j=0;j<N-1-i;j++)
        if(v[j]>v[j+1]){ string t=v[j]; v[j]=v[j+1]; v[j+1]=t; } }

10 — Counting sort
void countingSort(int v[], const int N, int mx){
    int conteggi[100]={0};
    for(int i=0;i<N;i++) conteggi[v[i]]++;
    int k=0;
    for(int val=0;val<=mx;val++)
        while(conteggi[val]-->0) v[k++]=val; }

Gli esercizi 2, 3, 4, 6, 7, 8 (ordina e cerca, conta confronti, valore assoluto, selection decrescente, k-esimo, fusione) seguono gli stessi schemi.