Learn Algorithm 5

February 20, 2025

Algortimi di ricerca

  • Ricercare elementi all'interno di una struttura dati,
  • Si usa il suo valore e un proprietà che lo identifica.
  • Si può usare un accesso casuale o sequenziale.

Tuttavia, si richiede che equal rappresenti una relazione di equivalenza:

  1. riflessiva: equal (a, a)
  2. simmetrica: equal (a, b) = ⇒ equal (b, a)
  3. transitiva: equal (a, b) ∧equal (b, c) = ⇒ equal (a, c)

Ricerca lineare - Linear Search

Complessità: O(n)

  • I valori nella stuttura dai non importa che siano ordinati.
  • Scorre in modo sequenziale la struttura dati fino a trovare l'elemento cercato.

Esempio:

Indovia il numero che sto pensando in un range da 1 a 5?

Ipotizziamo 5 come la soluzione e vediamo quanti tentativi ci vogliono per indovinare.

  • Step 1: 1 sbalgiato
  • Step 2: 2 sbalgiato
  • …
  • Step 5: 5 corretto

Codice di esempio in python:


def linear_search(array, elem, eq = lambda x, y: x == y):
    for i in range(len(array)):
        if eq(array[i],elem):
            return i
    return -1

Andiamo a vedere altri 2 esempi calati nel codice

/*
Caso 1

Struttura dati = [31, -7, 2, 8, 44, 0, -1, 5]

Cerca il valore 8
Controlla: 31 → -7 → 2 → 8 ✓
Trova 8 in posizione 3
Restituisce 3


Caso 2:

Cerca il valore 99
Controlla: 31 → -7 → 2 → 8 → 44 → 0 → -1 → 5
Non trova 99 dopo aver controllato tutto l'array
Restituisce None
*/

Andiamo a vedere il codice in python con l'utilizzo della ricorsione


def linear_search_rec(array, x, start=None, to=None, eq = lambda x, y: x == y):
    if start is None or to is None:
        start = 0
        to = len(array)-1
    if start > to: return -1
    if eq(array[start], x): return start
    return linear_search_rec(array, x, start+1, to, eq)

Ricerca binaria

La ricerca binaria:

  • Complessità: O(log n) -> più efficiente della ricerca lineare O(n) per grandi dataset.
  • Richiede un array ordinato

Flusso:

  • Divide l'array a metà ad ogni passo
  • Confronta l'elemento centrale con il valore cercato
  • Scarta metà dell'array ad ogni iterazione
  • (L'algoritmo dimezza l'area di ricerca ad ogni passo, da cui la complessità O(log n).)
  • Con elementi duplicati si può restituire qualsiasi indice corrispondente all'elemento cercato e non necessariamente il primo o l'ultimo.

Esempio

indovia il numero che sto pensando in un range da 1 a 100 Ipotizziamo 100 come la soluzione e vediamo quanti tentativi ci vogliono per indovinare.

  • Step 1: 50 sbalgiato è piu alto
  • Step 2: 75 sbalgiato è piu alto
  • Step 3: 88 sbalgiato è piu alto
  • Step 4: 94 sabgliato è piu alto
  • Step 5: 97 sabgliato è piu alto
  • Step 6: 99 sbalgiato è piu alto
  • Step 7: 100 corretto

In questo caso il lineare avrebbe impiagato 100 step invece questo binario solamente 7

Codice di esempio in python:


def binary_search_iter(array, x, start, to, eq = lambda x, y: x == y, less = lambda x, y: x < y):
    while start <= to:
        m = (start + to) // 2
        if eq(array[m], x): return m
        elif less(array[m], x): start = m+1
        else: to = m-1
    return -1

def binary_search(array, x):
    return binary_search_iter(array, x, 0, len(array)-1)

Altri esempi

/*
strutturaDati = [1, 3, 5, 7, 9, 11, 13]


Se cercassimo 7:

1. Prima iterazione:
   - left = 0, right = 6
   - mid = (0 + 6) // 2 = 3
   - arr[3] = 7 → trovato! Ritorna 3

Se cercassimo 11:

1. Prima iterazione:

   - mid = 3
   - arr[3] = 7 < 11
   - left = mid + 1 = 4

2. Seconda iterazione:
   - left = 4, right = 6
   - mid = (4 + 6) // 2 = 5
   - arr[5] = 11 → trovato! Ritorna 5
*/

Andiamo a vedere il codice in python con l'utilizzo della ricorsione

def binary_search_recur(array, x, start, to, eq = lambda x, y: x == y, less = lambda x, y: x < y):
    if to < start: return -1
    if start == to:
        return start if eq(array[start], x)  else -1
    mid = start + (to - start)//2
    print(f"from={start}; to={to}; mid={mid}")
    if eq(array[mid], x): return mid
    elif less(array[mid], x): return binary_search_recur(array, x, mid+1, to)
    else: return binary_search_recur(array, x, start, mid-1)

Ricerca per iterpolazione

  • Similare al binary search,
  • Invece di dividere a metà usa una formula di interpolazione per stimare la posizione
  • Assume distribuzione uniforme dei dati

Complessità:

  • O(1) caso migliore
  • O(log log n) caso medio con dati uniformi
  • O(n) caso peggiore

Algoritmi di ordinamento

Selection Sort

  • Opera trovando ripetutamente il minimo elemento nella parte non ordinata dell'array e posizionandolo all'inizio.

complessita:

  • Caso medio/peggiore/migliore: O(n²)
  • Spazio: O(1)

Codice di esempio in python:

def min_index(a, index_from, index_to):
    min_idx = index_from
    for i in range(index_from+1, index_to):
        if a[i] < a[min_idx]:
            min_idx = i
    return min_idx

def selection_sort(a):
    for i in range(len(a)-1):
        min_idx = min_index(a, i, len(a))
        a[i], a[min_idx] = a[min_idx], a[i]

Esempio

/*
StrutturaDati = [64, 25, 12, 22, 11]

Passi dell'esempio:

[64, 25, 12, 22, 11] → [11, 25, 12, 22, 64] (trova 11)
[11, 25, 12, 22, 64] → [11, 12, 25, 22, 64] (trova 12)
[11, 12, 25, 22, 64] → [11, 12, 22, 25, 64] (trova 22)
[11, 12, 22, 25, 64] → [11, 12, 22, 25, 64] (trova 25)

Output: [11, 12, 22, 25, 64]

Complessità: O(n²) in tutti i casi.
*/

Insertion Sort

  • Funziona inserendo sequenzialmente ogni elemento nella posizione corretta all'interno della porzione già ordinata dell'array.

complessita:

  • Caso medio/peggiore (array ordinato al contrario): O(n²)
  • Caso migliore (array già ordinato): O(n)
  • Spazio: O(1)

Codice di esempio in python:

def insert_in_order(arr, n, e):
    pos = n
    while pos > 0 and arr[pos-1] > e:
        arr[pos] = arr[pos-1]
        pos -= 1
    arr[pos] = e

def insertion_sort(a):
    for i in range(1,len(a)):
        insert_in_order(a, i, a[i])

Esempio

/*
strutturaDati = [64, 25, 12, 22, 11]

Passi dell'esempio:

[64, 25, 12, 22, 11] → [25, 64, 12, 22, 11] (inserisce 25)
[25, 64, 12, 22, 11] → [12, 25, 64, 22, 11] (inserisce 12)
[12, 25, 64, 22, 11] → [12, 22, 25, 64, 11] (inserisce 22)
[12, 22, 25, 64, 11] → [11, 12, 22, 25, 64] (inserisce 11)

Output: [11, 12, 22, 25, 64]
*/

Bubble Sort

  • confronta ripetutamente coppie di elementi adiacenti
  • li scambia se sono nell'ordine sbagliato.

Complessità:

  • Best case (array ordinato): O(n)
  • Worst case: O(n²)

Info:

  • La presenza di elementi grandi all’inizio non è problematica in quanto questi raggiungo la parte finale dell’array in poche scansioni
  • La presenza di elementi piccoli alla fine invece è più problematica, in quanto questi si sposteranno di poco ad ogni scansione
flowchart factorial

Codice di esempio in python:

def bubble_sort(a):
    swap = True
    n = len(a)
    i = 0
    while swap and i < n-1:
        swap = False
        for j in range(n-1-i):
            if a[j] > a[j+1]:
                swap = True
                a[j], a[j+1] = a[j+1], a[j]
        i += 1

Codice Versione ricorsiva


def bubble_sort_recursive(arr, n=None): # Inizializzazione della dimensione al primo chiamata
if n is None:
n = len(arr)

    # Caso base: se la dimensione è 1 o meno, l'array è ordinato
    if n <= 1:
        return

    # Fase di "bolla": fa "galleggiare" l'elemento più grande fino alla fine
    for i in range(n-1):
        if arr[i] > arr[i+1]:
            arr[i], arr[i+1] = arr[i+1], arr[i]

    # Chiamata ricorsiva sulla porzione non ordinata (tutti tranne l'ultimo)
    bubble_sort_recursive(arr, n-1)

Esempio

strutturaDati = [64, 34, 25, 12, 22]

Passaggi degli esempi [64, 34, 25, 12, 22]:

[34, 25, 12, 22, 64] # 64 "galleggia" alla fine
[25, 12, 22, 34, 64] # 34 trova la sua posizione
[12, 22, 25, 34, 64] # 25 trova la sua posizione
[12, 22, 25, 34, 64] # Ultima passata per verificare

Output [12, 22, 25, 34, 64]

Merge Sort

Il merge sort è un algoritmo di ordinamento che usa la strategia divide-et-impera:

  • Divide l'array a metà ricorsivamente finché non ottiene singoli elementi
  • Merge (fonde) le parti ordinate in modo crescente
  • Opera out-of-place usando array temporanei per il merge

Caratteristiche principali:

  • Stabile (mantiene ordine relativo di elementi uguali)
  • Complessità sempre O(n log n)
  • Richiede memoria extra O(n)
  • Efficiente su input molto grandi
  • Parallelizzabile
flowchart factorial

Codice esempio con ricorsione in python

def merge(a, b, r):
    i, j, k = 0, 0, 0
    # print(f"merge {a} and {b} into {r}")
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            r[k] = a[i]
            i = i + 1
        else:
            r[k] = b[j]
            j = j + 1
        k = k + 1
    for i in range(i,len(a)):
        r[k] = a[i]
        k = k + 1
    for i in range(j,len(b)):
        r[k] = b[i]
        k = k + 1

def merge_sort(a):
    if len(a)<=1: return
    m = len(a)//2
    left = a[:m] # beware: it's a copy
    right = a[m:] # beware: it's a copy
    merge_sort(left)
    merge_sort(right)
    merge(left, right, a)

    while i < len(left):
        arr[k] = left[i]
        i += 1
        k += 1

    while j < len(right):
        arr[k] = right[j]
        j += 1
        k += 1

Esempio

Esempio passo-passo con [38, 27, 43, 3]:

Divide: [38, 27] [43, 3]
Divide ancora: [38] [27] [43] [3]
Merge: [27, 38] [3, 43]
Merge finale: [3, 27, 38, 43]

Output: [3, 27, 38, 43]

Quick Sort

Funzionamento QuickSort:

  • Scelta del pivot (solitamente primo elemento, elemento centrale o casuale)
  • Partizionamento dell'array intorno al pivot
  • Ricorsione sulle due parti (sinistra e destra del pivot)

Complessità:

  • Caso medio: O(n log n)

  • Caso peggiore: O(n²) quando:

  • Array già ordinato e pivot sempre minimo/massimo

  • Array ordinato al contrario

  • Tutti elementi uguali

Caso migliore: O(n log n)

def partition(a,start,to):
    pivot = a[start]
    k = start+1
    for i in range(start+1,to):
        if a[i] < pivot:
            a[i], a[k] = a[k], a[i]
            k += 1
    a[start] = a[k-1]
    a[k-1] = pivot
    return k-1

# sort array
def quick_sort(array, start=None, to=None):
    start = 0 if start==None else start
    to = len(array) if to==None else to
    if start < to:
        pivot_index = partition(array,start,to)
        quick_sort(array,start,pivot_index)
        quick_sort(array,pivot_index+1,to)
    return quick_sort(lesser) + equal + quick_sort(greater)

    // Esempio di utilizzo

    arr = [3, 6, 8, 10, 1, 2, 1]
    print("Array originale:", arr)
    sorted_arr = quick_sort(arr)
    print("Array ordinato:", sorted_arr)

    // Processo di partizionamento per arr = [3,6,8,10,1,2,1]:
    // Pivot = 3
    // lesser = [1,2,1] # elementi < 3
    // equal = [3] # elementi = 3
    // greater = [6,8,10] # elementi > 3
    // Ricorsione su [1,2,1]:
    // Pivot = 1
    // lesser = []
    // equal = [1,1]
    // greater = [2]
    // Ricorsione su [6,8,10]:
    // Pivot = 6
    // lesser = []
    // equal = [6]
    // greater = [8,10]

Il pivot è un elemento dell'array scelto come riferimento per il partizionamento. Intorno ad esso, l'array viene riorganizzato in modo che:

elementi minori del pivot vadano a sinistra elementi maggiori del pivot vadano a destra

Altro esempio

/*
Passo 1: Pivot = 7
[7] 2 1 6 8 5 3 4
Partizionamento:
[2,1,6,5,3,4] [7] [8]

Passo 2: Lavoro sulla parte sinistra, pivot = 2
[2] 1 6 5 3 4
Partizionamento:
[1] [2] [6,5,3,4]

Passo 3: Lavoro sulla parte [6,5,3,4], pivot = 6
[6] 5 3 4
Partizionamento:
[5,3,4] [6] []

Passo 4: Lavoro su [5,3,4], pivot = 5
[5] 3 4
Partizionamento:
[3,4] [5] []

Passo 5: Lavoro su [3,4], pivot = 3
[3] 4
Partizionamento:
[] [3] [4]

Risultato finale:
[1] [2] [3] [4] [5] [6] [7] [8]
*/

Taballa comparativa tra i vari algoritmi visti finora

flowchart factorial

### **See you in the next post! Stay Tuned!**