Appunti completi per Algoritmi e Programmazione ad oggetti

Algoritmi di ordinamento

Definizione del problema

Input: Una sequenza di n numeri: 1, a₂, ..., a_n>.

Output: Una permutazione della sequenza di ingresso: tale che 1', a_2', ..., a_n'> con a_1' < a_2' < ... < a_n'.

Nota bene: Gli algoritmi di ordinamento sono spesso descritti su array di interi o elenchi in Python, ma la stessa logica si applica anche quando ogni record contiene un insieme di dati. In questi casi, la sequenza viene ordinata in base a una chiave di ordinamento (ad esempio, persone ordinate per età).

Stabilità

Un algoritmo di ordinamento è stabile se gli eventuali elementi con chiavi uguali mantengono l'ordine relativo. Ad esempio: un elenco di record composto da un numero e da un carattere alfabetico è ordinato secondo il numero.

Input: (3,z) (5,c) (3,a) (4,a)

Quando eseguiamo un ordinamento stabile, l'elemento (3,z) precede (3,a) poiché sono uguali per la chiave numerica, ma la loro posizione relativa viene mantenuta.

Output ordinato stabile: (3,z) (3,a) (4,a) (5,c)

Output ordinato instabile: (3,a) (3,z) (4,a) (5,c)

La stabilità è una caratteristica importante in alcuni algoritmi di ordinamento, specialmente quando si lavora con record complessi o quando l'ordinamento deve rispettare l'ordine originale degli elementi con chiavi uguali. Algoritmi come Merge Sort e Bubble Sort sono stabili, mentre algoritmi come Quick Sort (nelle sue implementazioni base) sono instabili.

Insertion Sort

L'Insertion Sort è un algoritmo di ordinamento semplice che costruisce gradualmente una sequenza ordinata un elemento alla volta, "inserendo" gli elementi nella loro posizione corretta. È simile al modo in cui si ordina una mano di carte, in cui ogni carta viene inserita al posto giusto rispetto alle altre già ordinate.

def insertion_sort(a):
    for i in range(1, len(a)):
        k = i
        key = a[i]
        while k > 0 and key 

Complessità dell'Insertion Sort

L'algoritmo è semplice ma ha una complessità computazionale che varia a seconda del caso (caso migliore, caso peggiore e caso medio):

• Ciclo esterno: Iterazioni: sempre n - 1 iterazioni, dove n è il numero di elementi nella lista. Il ciclo esterno è sempre eseguito una volta per ogni elemento della sequenza, a partire dal secondo fino all'ultimo.
• Ciclo interno: Caso peggiore: per ogni iterazione del ciclo esterno, il ciclo interno può dover confrontare e spostare ogni elemento a sinistra, il che comporta un numero di iterazioni pari a i, dove i è l'indice dell'iterazione del ciclo esterno.
• Le operazioni di confronto (nel caso peggiore) sono stimate come: 1/2 (n² + n) - 1/2.
• Le operazioni di copia (nel caso peggiore) sono stimate come: 1/2 (n² + 3n - 4).

La complessità totale, rappresentata dalla funzione O(n²), è la somma del numero di operazioni svolte. Il tempo di esecuzione nel caso peggiore è O(n²). La complessità quadratica emerge dal fatto che ogni elemento (nel caso peggiore) potrebbe essere confrontato con tutti i precedenti, risultando in un numero di operazioni proporzionale a n². Il caso migliore si verifica quando l'array è già ordinato, in cui il ciclo interno eseguirà un solo confronto per ogni elemento, risultando in una complessità lineare O(n). In questo caso, non sono necessarie operazioni di copia, ma solo i confronti.

Complessità d'ordinamento

La complessità degli algoritmi di ordinamento varia a seconda del metodo utilizzato e delle caratteristiche specifiche dell'input (come dimensione e distribuzione dei dati).

O(n²) - Algoritmi semplici e iterativi

• Questi algoritmi confrontano e spostano elementi ripetutamente, utilizzando spesso due cicli annidati, uno per iterare sull'array e l'altro per inserire o spostare elementi all'interno della lista. Ad esempio:
  • Insertion Sort: Adatto per piccole liste o per liste quasi ordinate.
  • Selection Sort: Trova il minimo (o massimo) elemento e lo posiziona al suo posto, ripetendo l'operazione fino alla fine.
  • Bubble Sort: Scambia elementi adiacenti per spostare progressivamente il più grande verso la fine della lista.
• Questi algoritmi sono di solito semplici da implementare ma diventano inefficaci su liste grandi a causa della complessità quadratica.

O(n log n) - Algoritmi complessi e ricorsivi

• La complessità O(n log n) deriva da algoritmi che dividono ricorsivamente la lista e ordinano ogni sottolista, combinandole alla fine per ottenere il risultato finale. Questa classe di complessità è il miglior compromesso possibile per gli algoritmi di ordinamento generali basati su confronti. Ad esempio:
  • Merge Sort: Divide la lista a metà fino a ottenere singoli elementi e poi li ricombina in modo ordinato.
  • Heapsort: Costruisce un albero binario in cui ogni nodo è maggiore (o minore) dei suoi figli, e poi estrae progressivamente l'elemento massimo (o minimo).
  • Quicksort: Seleziona un elemento pivot e organizza gli altri elementi rispetto ad esso, suddividendo l'array in parti minori che vengono ordinate ricorsivamente.
• Questi algoritmi sono tra i più efficienti e comunemente utilizzati per ordinare grandi dataset.

O(n) - Algoritmi per casi speciali

• Questi algoritmi possono ordinare elementi in O(n), ma sono applicabili solo a dati con determinate caratteristiche, come un intervallo numerico ristretto o una rappresentazione che permette operazioni basate su posizioni o bucket. Ad esempio:
  • Counting Sort: Utile quando gli elementi sono numeri interi di un intervallo noto e limitato.
  • Radix Sort: Utilizza i valori di posizione (cifre) per ordinare progressivamente elementi multi-cifra (ad esempio, numeri o stringhe).
  • Bucket Sort: Suddivide gli elementi in "secchi" (bucket) per poi ordinare individualmente i bucket.
• Questi algoritmi sono molto efficienti su input specifici, ad esempio quando si lavora con interi non negativi entro un intervallo ristretto o quando si ordinano elementi come chiavi hash.

Counting Sort

Il Counting Sort è un algoritmo di ordinamento basato sul conteggio delle occorrenze di ciascun valore all'interno di un intervallo limitato (ad esempio, numeri tra 0 e k-1). Funziona bene quando i valori sono numeri interi con una gamma limitata rispetto al numero di elementi da ordinare.

Idea: Per ogni elemento nell'array di input, si determina quanti elementi sono minori di esso, calcolando così la posizione finale di ciascun elemento nell'array ordinato.

Algoritmo Counting Sort

1. Preparazione dei dati: Si iniziano tre array:
   • Array di ingresso con i dati originali.
   • Array di output dove saranno memorizzati i dati ordinati.
   • Array ausiliario (per il conteggio delle occorrenze di ciascun valore).
2. Conteggio delle occorrenze: L'array ausiliario viene popolato con il numero di volte in cui ogni numero appare nell'array di ingresso.
3. Calcolo delle posizioni finali: Ogni posizione dell'array ausiliario viene aggiornata per riflettere la quantità di numeri uguali o inferiori a ciascun valore; questo passo permette di sapere dove posizionare ogni elemento nell'output.
4. Costruzione dell'array ordinato: Per ogni elemento nell'array di ingresso, si colloca l'elemento nella posizione corretta nell'array di output, decrementando il contatore nell'array ausiliario per ciascun elemento piazzato.

def counting_sort(arr, max_value):
    count = [0] * (max_value + 1)
    for num in arr:
        count[num] += 1
    for i in range(1, len(count)):
        count[i] += count[i - 1]
    output = [0] * len(arr)
    for num in reversed(arr):
        output[count[num] - 1] = num
        count[num] -= 1
    return output

Complessità: O(n + k), dove n è il numero di elementi e k è il range dei valori possibili.

Merge Sort

Il Merge Sort è un algoritmo di ordinamento ricorsivo che segue l'approccio divide et impera. È adatto per dataset grandi.

Idea: Divide l'array in due metà, ordina ciascuna metà ricorsivamente e poi unisce le due metà ordinate in un array finale ordinato.

def merge_sort(arr):
    if len(arr) 

Complessità: O(n log n), poiché ad ogni livello la lista viene divisa e unita.

Quicksort

Il Quicksort è un algoritmo di ordinamento veloce e ricorsivo che funziona bene su array di grandi dimensioni.

Idea: Sceglie un elemento chiamato pivot e riordina l'array in modo tale che tutti gli elementi minori del pivot siano alla sua sinistra, e tutti quelli maggiori siano alla sua destra.

Algoritmo Quicksort

1. Selezione del pivot: Il pivot può essere scelto in vari modi (random, mediana, etc.). La scelta del pivot è cruciale per l'efficienza dell'algoritmo.
2. Partitioning:
   • Si percorre l'array da sinistra alla ricerca di un valore maggiore del pivot e da destra alla ricerca di un valore minore del pivot.
   • I valori trovati vengono scambiati tra loro.
   • Questo si ripete fino a completare la partizione intorno al pivot, che finirà nella sua posizione finale.
3. Ordinamento delle partizioni: Le due partizioni risultanti vengono ordinate ricorsivamente utilizzando la stessa procedura.