utfcode

[Link] 3.10 UTF-8 input encoding 13.06.2000

scanner for code UTF-8 installed.

1
 I Vettori in Informatica
Concetti, Algoritmi Fondamentali e Analisi di Complessità

Appunti di Informatica
21 luglio 2026

Indice
1 Concetto e Definizione di Vettore 3

2 Vettore di N Elementi e Controllo sulla Dimensione 3

3 Caricamento e Stampa 3

4 Algoritmi Fondamentali 4
4.1 Estrazione di elementi in base a condizioni . . . . . . . . . . . . . . . . . . 4
4.2 Calcolo di Minimo, Massimo e Media . . . . . . . . . . . . . . . . . . . . . 4
4.3 Modifica degli elementi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
4.4 Cancellazione ed Inserimento . . . . . . . . . . . . . . . . . . . . . . . . . . 5
4.4.1 Cancellazione in posizione pos (Shift a sinistra) . . . . . . . . . . . 5
4.4.2 Inserimento in posizione pos (Shift a destra) . . . . . . . . . . . . . 5
4.5 Gestione di Vettori Paralleli . . . . . . . . . . . . . . . . . . . . . . . . . . 6

5 Algoritmi di Ricerca 6
5.1 Ricerca Sequenziale (o Lineare) . . . . . . . . . . . . . . . . . . . . . . . . 6
5.2 Ricerca Binaria (o Dicotomica) . . . . . . . . . . . . . . . . . . . . . . . . 6

6 Ordinamento: Bubble Sort 7

6.1 Regola di Scambio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
6.2 Codice C++ Ottimizzato . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

7 Tabella Riassuntiva della Complessità Computazionale 8

2
 1 Concetto e Definizione di Vettore
Un vettore (o array monodimensionale) è una struttura dati omogenea, sequenziale e ad
accesso diretto.

• Omogenea: Tutti gli elementi contenuti sono del medesimo tipo di dato.

• Sequenziale: Gli elementi sono memorizzati in posizioni di memoria contigue.

• Accesso diretto: È possibile accedere a un qualunque elemento indicando il suo

indice, con un costo temporale costante O(1).

Formale matematicamente, un vettore V di dimensione N si definisce come un’ap-

plicazione da un insieme finito di indici verso l’insieme dei valori ammissibili dal tipo di
dato:
V : {0, 1, 2, . . . , N − 1} → TipoDati
L’accesso all’elemento i-esimo avviente tramite la notazione V [i], con vincolo:

0≤i<N

2 Vettore di N Elementi e Controllo sulla Dimensio-

ne
In molti linguaggi a tipizzazione statica, la dimensione massima fisica del vettore (M AX)
deve essere allocata a tempo di compilazione. L’utente, tuttavia, lavora spesso con una
dimensione logica N ≤ M AX.
Per prevenire errori di Buffer Overflow e accessi a memoria non autorizzata, la dimen-
sione N deve essere convalidata con un ciclo di controllo:
1 const int MAX = 100;
2 int V [ MAX ];
3 int N ;
4

5 // Input controllato per la dimensione N

6 do {
7 cout << " Inserisci la dimensione N (1 - " << MAX << " ) : " ;
8 cin >> N ;
9 } while ( N < 1 || N > MAX ) ;
Listing 1: Controllo sulla dimensione dell’array
—

3 Caricamento e Stampa
Le operazioni di caricamento (popolamento) e stampa richiedono la scansione sequenziale
di tutti gli N elementi. La loro complessità temporale è lineare: O(N ).

3
 1 // Algoritmo di Caricamento
2 for ( int i = 0; i < N ; i ++) {
3 cout << " V [ " << i << " ] = " ;
4 cin >> V [ i ];
5 }
6

7 // Algoritmo di Stampa
8 for ( int i = 0; i < N ; i ++) {
9 cout << " V [ " << i << " ] = " << V [ i ] << endl ;
10 }
Listing 2: Caricamento e Stampa di un vettore
—

4 Algoritmi Fondamentali
4.1 Estrazione di elementi in base a condizioni
Data una proprietà P (x), si filtrano gli elementi di V copiandoli in un secondo vettore
W:
W = {V [i] | 0 ≤ i < N ∧ P (V [i]) = true}

1 int W [ MAX ];
2 int k = 0; // Dimensione del vettore W
3

4 for ( int i = 0; i < N ; i ++) {

5 if ( V [ i ] % 2 == 0) { // Condizione P ( x ) : elemento pari
6 W [ k ] = V [ i ];
7 k ++;
8 }
9 }
Listing 3: Estrazione elementi pari

4.2 Calcolo di Minimo, Massimo e Media

Sia V un vettore non vuoto di N elementi:

• Massimo: M = max0≤i<N V [i]

• Minimo: m = min0≤i<N V [i]

P −1
• Media aritmetica: µ = N1 N i=0 V [i]

1 int maxVal = V [0];

2 int minVal = V [0];
3 double somma = 0;
4

5 for ( int i = 0; i < N ; i ++) {

6 if ( V [ i ] > maxVal ) maxVal = V [ i ];
7 if ( V [ i ] < minVal ) minVal = V [ i ];

4
 8 somma += V [ i ];
9 }
10 double media = somma / N ;
Listing 4: Minimo, Massimo e Media

4.3 Modifica degli elementi

Consiste nell’applicare una funzione f (x) a ciascun elemento del vettore:

V [i] ← f (V [i]), ∀i ∈ {0, . . . , N − 1}

1 for ( int i = 0; i < N ; i ++) {

2 V [ i ] = V [ i ] * 2; // Raddoppia il valore di ogni elemento
3 }
Listing 5: Modifica degli elementi

4.4 Cancellazione ed Inserimento

4.4.1 Cancellazione in posizione pos (Shift a sinistra)
V [i] ← V [i + 1], ∀i ∈ {pos, . . . , N − 2}

1 int pos = 2; // Indice da eliminare

2 for ( int i = pos ; i < N - 1; i ++) {
3 V [ i ] = V [ i + 1];
4 }
5 N - -; // Riduzione della dimensione logica
Listing 6: Cancellazione elemento

4.4.2 Inserimento in posizione pos (Shift a destra)

V [i + 1] ← V [i], ∀i ∈ {N − 1, . . . , pos}

1 int pos = 2;
2 int val = 99;
3 for ( int i = N - 1; i >= pos ; i - -) {
4 V [ i + 1] = V [ i ];
5 }
6 V [ pos ] = val ;
7 N ++; // Incremento della dimensione logica
Listing 7: Inserimento elemento

5
 4.5 Gestione di Vettori Paralleli
Due o più vettori sono detti paralleli quando gli elementi collocati nello stesso indice i
si riferiscono alle diverse proprietà della medesima entità.
1 string nomi [ MAX ] = { " Anna " , " Luca " , " Marco " };
2 int voti [ MAX ] = {28 , 24 , 30};
3

4 for ( int i = 0; i < N ; i ++) {

5 cout << nomi [ i ] << " ha ottenuto il voto : " << voti [ i ] <<
endl ;
6 }
Listing 8: Esempio vettori paralleli
—

5 Algoritmi di Ricerca
5.1 Ricerca Sequenziale (o Lineare)
Scorrendo il vettore elemento per elemento, confronta il valore cercato target.

• Caso Migliore: O(1)

• Caso Peggiore/Medio: O(N )

1 int target = 15;

2 int pos = -1;
3 for ( int i = 0; i < N ; i ++) {
4 if ( V [ i ] == target ) {
5 pos = i ;
6 break ; // Interrompe appena trovato
7 }
8 }
Listing 9: Ricerca Sequenziale

5.2 Ricerca Binaria (o Dicotomica)

Applicabile **solo se il vettore è già ordinato**. Sfrutta il paradigma Divide et Impera.
Siano low e high gli estremi dell’intervallo di ricerca:
 
low + high
mid =
2

• Se V [mid] = target, elemento trovato.

• Se V [mid] < target, aggiorna low ← mid + 1.

• Se V [mid] > target, aggiorna high ← mid − 1.

Complessità Temporale: O(log2 N ) nel caso peggiore.

6
 1 int target = 15;
2 int low = 0 , high = N - 1;
3 int pos = -1;
4

5 while ( low <= high ) {

6 int mid = low + ( high - low ) / 2;
7 if ( V [ mid ] == target ) {
8 pos = mid ;
9 break ;
10 }
11 if ( V [ mid ] < target ) low = mid + 1;
12 else high = mid - 1;
13 }
Listing 10: Ricerca Binaria
—

6 Ordinamento: Bubble Sort

Il **Bubble Sort** è un algoritmo basato sullo scambio continuo di elementi adiacenti
non ordinati.

6.1 Regola di Scambio

Per ogni i ∈ {0, . . . , N − 2}:

se V [i] > V [i + 1] =⇒ swap(V [i], V [i + 1])

6.2 Codice C++ Ottimizzato

1 bool scambiato ;
2 for ( int i = 0; i < N - 1; i ++) {
3 scambiato = false ;
4 for ( int j = 0; j < N - 1 - i ; j ++) {
5 if ( V [ j ] > V [ j + 1]) {
6 int temp = V [ j ];
7 V [ j ] = V [ j + 1];
8 V [ j + 1] = temp ;
9 scambiato = true ;
10 }
11 }
12 // Se non ci sono stati scambi , il vettore e gia ordinato
13 if (! scambiato ) break ;
14 }
Listing 11: Bubble Sort Ottimizzato
—

7
7 Tabella Riassuntiva della Complessità Computa-
zionale

Operazione / Algoritmo Caso Migliore Caso Medio Caso Peggiore

Accesso diretto O(1) O(1) O(1)
Inserimento / Cancellazione O(1) O(N ) O(N )
Ricerca Sequenziale O(1) O(N ) O(N )
Ricerca Binaria O(1) O(log N ) O(log N )
Bubble Sort O(N ) O(N 2 ) O(N 2 )

Tabella 1: Confronto delle prestazioni temporali.