Resumos

Apontamentos universitários em formato Markdown do Obsidian.

Algoritmi di ordinamento quadratico

Problemi di ricerca

Ricerca lineare ⇒ no requisiti sul dato → O(n)
Ricerca binaria ⇒ array ordinato → O(log₂ n), da aggiungere il costo di ordinamento
Ricerca uniforme ⇒ array ordinato → O(n) se la distribuzione è uniforme allora circa O(1)
Tabelle Hash ⇒
- necessità di chiave di ricerca
- generare la struttura dati → O(n)
→ O(1) se funzione hash e fattore di carico sono scelti bene
Alberi binari di ricerca ⇒
- costruzione dell'albero
- bilanciamento albero
→ O(log₂ n)

Algoritmi di ricerca

Bubble Sort

bool scambio; int x = n; int last = 0;
do {
scambio = false;
for(int i = 0; i < x-1; i++) {
    if(a[i] > a[i+1]) {
        tmp = a[i];
        a[i] = a[i+1];
        a[i+1] = tmp;
        scambio = true;
        last = i+1;
    }
}
x = last;
} while(scambio)

CASO PEGGIORE: O(n²)
CASO MIGLIORE: O(n)

Si contraddistingue nell'avere un elevato numero di istruzioni elementari che nel caso peggiore incrementano, in qualche modo, il "peso" della complessità.

(n-1) + (n-2) + (n-3) + ... + 1 ⇒ n(n+1)/2 = ~ O(n²)

Selection Sort

for(int i = 0; i < n-1; i++) {
int min = i;
for(int j = i+1; j < n; j++) {
    if(a[j] < a[min]) {
        min = j;
    }
}
int temp = a[min];
a[min] = a[i];
a[i] = temp;
}

CASO PEGGIORE: O(n²)
CASO MIGLIORE: O(n²)

A differenza del Bubble Sort, il numero di istruzioni elementari viene eseguito n volte e non n² volte. Quindi in un certo senso questo algoritmo è migliore.

Insertion Sort

for(int i = 0; i < n; i++) {
temp = a[i];
j = i-1;
while(j >= 0 && a[j] > temp) {
    a[j+1] = a[j];
    j--;
}
a[j+1] = temp;
}

CASO PEGGIORE: O(n²) (array al contrario)
CASO MIGLIORE: O(n)

Ipotizzando un caso intermedio, l'esecuzione del ciclo while si interrompe prima dell'indice j. Quindi il numero di iterazioni del while sarà minore del ciclo for del Selection Sort.

Inoltre non vengono fatti scambi ma bensì uno shifting sinistro e infine il numero di operazioni di base è inferiore ai precedenti algoritmi.

Merge Sort: è una classica applicazione della tecnica divide et impera. Dato un vettore di n elementi si suddivide in due parti. A questo punto si ordinano ricorsivamente i due vettori e quindi il vettore complessivo viene ordinato per "fusione" dei due sotto-vettori.
```
void mergeSort(Vettore<T>& v, int in, int fin) {
if((fin-in) < 20) {
    insertionSort(V, in, fin);
} else {
    int medio = (in + fin)/2;
    mergeSort(v, in, medio);
    mergeSort(v, medio+1, fin);
    merge(v, in, fin, medio);
}
}
```

void merge(Vettore& v, int in, int fin, int medio) { Vettore a(1, fin-in+1); int medio1 = medio + 1; int i1 = in; int i2 = mredio + 1; int i3 = 1; while((i1 <= medio && i2 <= fin)) { if(v[i1] < v[i2]) { a[i3] = v[i1]; i1++; } else { a[i3] = v[i2]; i2++; } i3++; }

while(i1 <= medio) {
    a[i3] = v[i1];
    i1++;
    i3++;
}

while(i2 <= fin) {
    a[i3] = v[i2];
    i2++;
    i3++;
}

for(i3 = 1; i1 = in; i1 <= fin; i3++, i1++) {
    v[i1] = a[i3];
}

}


Questo algoritmo ha una complessità pari a O(n·log₂ n) sia nel caso peggiore che in quello migliore. L'unica differenza rispetto ai precedenti è che non è *ON SITE*, cioè si appoggia su una struttura dati ausiliare e compie un grande numero di istruzioni elementari.

- **Quick Sort**: si prende in esame un elemento *x* del vettore e si determina la posizione esatta che gli compete nell'ordinamento. Contemporaneamente si portano alla sua sinistra tutti gli elementi che lo precedono e alla sua destra quelli che lo seguono ottenendo così due sotto-vettori *v1* e *v2*.

A questo punto, con la stessa tecnica, si procede ad esaminare gli altri sotto-vettori. L'algoritmo cruciale è la partizione del vettore.

A tale scopo si scandisce da sinistra a destra fino a che non si trova un elemento *y* che segue il nostro elemento e contemporanemante si scandisce da destra a sinistra fino a che non si trova un numero minore (*z*).

A questo punto, *y* e *z* si scambiano.
```cpp
void quickSort(Vettore<T>& v, int in, int fin) {
    if((fin - in) < 20)
        insertionSort(v, in, fin);
    else {
        int PosOrd = partiziona(v, in, fin);
        quickSort(v, in, PosOrd-1);
        quickSort(v, PosOrd+1, fin);
    }
}

int partiziona(Vettore<T>& v, int in, int fin) {
    int i = in; int j = fin + 1;
    while(i < j) {
        do j--;
        while(v[in] < v[j]);

        do i++;
        while(v[in] >=  v[i] && i < j);

        if(i < j) scambia(v[i], v[j]);
        scambia(v[in], v[j]);
        return j;
    }
}

La complessità dipende dalla funzione partiziona. In generale è O(n) ma adesso il numero di suddivisioni non è più costante come nel Merge Sort. Possiamo infatti individuare 3 complessità:

CASO MIGLIORE: O(n·log n) (array disordinato)
CASO PEGGIORE: O(n²) (array ordinato)
CASO MEDIO: O(n·log₂ n) (array abbastanza disordinato)

Per evitare di ricadere nel caso peggiore paradossalmente basta disordinare il nostro array così da migliorare le prestazioni. In termini di costanti questo è migliore del Merge Sort ed è ON SITE.