Appunti completi per Algoritmi e Programmazione ad oggetti

ALGORITMI DI ORDINAMENTO

Definizione del problema:

Input: Una sequenza di n numeri:

 <a , a , ..., a >.

1 2 n

Output: Una permutazione della sequenza di ingresso: tale che

 <a , a , ..., a > a < a <

1' 2' n' 1' 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à).

S

TABILITÀ

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 è ordinata

secondo il numero

INPUT:

 (3,z) (5,c) (3,a) (4,a)

Quando eseguiamo un ordinamento stabile, l'elemento precede poiché sono uguali

(3,z) (3,a)

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.

I S

NSERTION ORT

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 < a[k-1]:

a[k] = a[k-1]

k -= 1

a[k] = key

Complessità

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.

o Il ciclo esterno è sempre eseguito una volta per ogni elemento della sequenza, a partire

o dal secondo fino all'ultimo.

CICLO INTERNO:

 Caso peggiore: per ogni iterazione del ciclo esterno, il ciclo interno può dover confrontare e

o 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:

13

Politecnico di Torino [ALGORITMI E PROGRAMMAZIONE A OGGETTI]

1 ( + ) − 1

2

Le operazioni di copia (nel caso peggiore) sono stimate come:

1 ( + 3 − 4)

2

Questi numeri rappresentano la quantità di dati che devono essere spostati, che è una parte

fondamentale dell'algoritmo. La complessità totale, rappresentata dalla funzione è la somma del

(),

numero di operazioni svolte: ( − 1)

(

() = 1 + 2 + − 1) = = −

2 2 2

Il tempo di esecuzione nel caso peggiore è 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 . 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 In

().

questo caso, non sono necessarie operazioni di copia, ma solo i confronti.

C ’

OMPLESSITÀ 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 itera vi

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: 14

Politecnico di Torino [ALGORITMI E PROGRAMMAZIONE A OGGETTI]

 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.

C OUNTING 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 e Funziona bene quando i valori sono

0 − 1).

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 calcolando così

,

la posizione finale di nell'array ordinato.

Algoritmo

1. PREPARAZIONE DEI DATI: si iniziano tre array:

Array di ingresso con i dati originali.

o Array di output dove saranno memorizzati i dati ordinati.

o Array ausiliario (per il conteggio delle occorrenze di ciascun valore).

o

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À: dove è il numero di elementi e è il range dei valori possibili.

( + ),

M ERGESORT

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.

Algoritmo

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: 15

Politecnico di Torino [ALGORITMI E PROGRAMMAZIONE A OGGETTI]

a. 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.

b. I valori trovati vengono scambiati tra loro.

c. 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.

def merge_sort(arr):

if len(arr) <= 1:

return arr

mid = len(arr) // 2

left_half = merge_sort(arr[:mid])

right_half = merge_sort(arr[mid:])

return merge(left_half, right_half)

def merge(left, right):

result = []

i = j = 0

while i < len(left) and j < len(right):

if left[i] < right[j]:

result.append(left[i])

i += 1

else:

result.append(right[j])

j += 1

result.extend(left[i:])

result.extend(right[j:])

COMPLESSITÀ: poiché ad ogni livello la lista viene divisa e unita.

( log )

Q UICKSORT

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

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:

a. 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.

b. I valori trovati vengono scambiati tra loro.

c. Questo si ripete fino a c