Trippel sort
# Trippel sort

Trippel sort (conosciuto anche come stooge sort) rientra nel gruppo dei peggiori algoritmi di ordinamento ed è per questo motivo poco conosciuto. A fronte di una forte inefficienza, l'algoritmo ha valore per scopi didattici ma non trova utilizzi pratici negli ordinamenti veri e propri.

## Descrizione

L'algoritmo viene presentato nella sua forma ricorsiva, che è molto semplice.

L'idea alla base dell'algoritmo è di dividere l'insieme da ordinare in due punti, suddividendone la dimensione in tre parti, di cui quella centrale grande almeno quanto le altre due. Si creano due sottoinsiemi di dimensione 2/3 che si sovrappongono per 1/3.

Successivamente vengono fatti tre ordinamenti: prima si ordinano (ricorsivamente) i primi 2/3 dell'insieme, poi i secondi 2/3, poi nuovamente i primi 2/3.

L'algoritmo si ripete quindi su dimensioni più piccole, circa 2/3, fino a quando non arriva a coppie di due elementi, che vengono ordinate con un confronto ed un eventuale scambio. Dato che l'insieme è suddiviso in sottoinsiemi che sono almeno 2/3 di quello precedente non si otterranno mai insiemi più piccoli di una coppia.

## Variante 1 (originale)

Questa è la variante originale, descritta in codice Basic.

Nelle stime il valore 2.71 è un valore arrotondato che sta per $log_{1.5}$ 3.

| Caratteristiche | ricorsiva, in loco, non stabile, non parallelizzabile | ricorsiva, in loco, non stabile, non parallelizzabile | ricorsiva, in loco, non stabile, non parallelizzabile |
| - | - | - | - |
| Strutture dati | vettori | vettori | vettori |
| Casi | migliore | medio | peggiore |
| Memoria | Ω(log n) | Θ(log n) | Ο(log n) |
| Tempo | $Ω(n^{2.71})$ | $Θ(n^{2.71})$ | $Ο(n^{2.71})$ |
| Confronti | C(n) = $∑_{i=0...k}$ $3^k$ , per n ≥ $n_k$ | C(n) = $∑_{i=0...k}$ $3^k$ , per n ≥ $n_k$ | C(n) = $∑_{i=0...k}$ $3^k$ , per n ≥ $n_k$ |
| Scambi | 0 | ≅S(n) / 2 | S(n) |

### Analisi dei confronti

Si veda prima l'analisi della variante 2, analisi che è più semplice e introduttiva a questa.

Per ogni valore di n, C(n) è costante qualunque sia l'ordine degli elementi, e vale esattamente:

$C_0=$ 1 $C_k=$ $C_{k-1}$ * 3 + 1 cioè $C_k=$ $∑_{i=0...k}$ $3^k$

per n ≥ $n_k$ , dove $n_0$ = 2 $n_1$ = 3 $n_k$ = $ceil(n_{k-1}$ * 1.5) - 1

(la funzione ceil(x) indica il valore di x arrotondato all'intero superiore)

n=2 ↔ C=1 n=3 ↔ C=4 n=4 ↔ C=13 n≥5 ↔ C=40 n≥7 ↔ C=121 n≥10 ↔ C=364 n≥14 ↔ C=1093 n≥20 ↔ C=3280 …

(si veda la variante 2 per un approfondimento)

se si approssima

$3^k+3^{k-1}+...$ con $3^k$ allora C(n) ≈ $n^{2.71}$ come per la variante 2.

### Analisi degli scambi

S(n) = (n - 1) * (n - 2) / 2 + 1 - $Δ_k$ , per n ≥ $n_k.$

$Δ_1$ = 1 per $n_1=$ 8 $Δ_2$ = ? per $n_2$ = ? …

n=2 ↔ S=1 , $S_{medio}=0.50$ n=3 ↔ S=2 , $S_{medio}=1.17$ n=4 ↔ S=4 , $S_{medio}=2.17$ n=5 ↔ S=7 , $S_{medio}=3.57$ n=6 ↔ S=11 , $S_{medio}=5.60$ n=7 ↔ S=16 , $S_{medio}=7.99$ n=8 ↔ S=21 , $S_{medio}=10.63$ n=9 ↔ S=28 , $S_{medio}=14.14$ n=10 ↔ S=36 , $S_{medio}=18.13$ …

## Variante 2 (riduzione dei confronti)

Questa è una versione migliorata. Poiché i confronti (e scambi) vengono comunque fatti quando i gruppi sono ridotti a coppie, si effettuano solo in questo caso. Questo riduce molto il numero di confronti e aumenta un po' il numero di scambi.

La variante diventa stabile.

| Caratteristiche | ricorsiva, in loco, stabile, non parallelizzabile | ricorsiva, in loco, stabile, non parallelizzabile | ricorsiva, in loco, stabile, non parallelizzabile |
| - | - | - | - |
| Strutture dati | vettori | vettori | vettori |
| Casi | migliore | medio | peggiore |
| Memoria | Ω(log n) | Θ(log n) | Ο(log n) |
| Tempo | $Ω(n^{2.71})$ | $Θ(n^{2.71})$ | $Ο(n^{2.71})$ |
| Confronti | C(n) = $3^k,$ per n ≥ $n_k$ | C(n) = $3^k,$ per n ≥ $n_k$ | C(n) = $3^k,$ per n ≥ $n_k$ |
| Scambi | 0 | n * (n - 1) / 4 | n * (n - 1) / 2 |

### Analisi dei confronti

Per ogni valore di n, C(n) è costante qualunque sia l'ordine degli elementi.

Il valore di C(n) è del tipo $3^k$ e aumenta a scaglioni all'aumentare di n.

I valori di n per i quali C(n) cambia sono: 2,3,4,5,7,10,14,20,29,43,64,95,142,212,317,475,712...

n=2 ↔ C=1 n=3 ↔ C=3 n=4 ↔ $C=3^2$ n≥5 ↔ $C=3^3$ n≥7 ↔ $C=3^4$ n≥10 ↔ $C=3^5$ …

da cui si ricava la relazione

$C_k=$ $3^k,$ per n ≥ $n_k$

dove $n_0$ = 2 $n_1$ = 3 $n_k$ = $ceil(n_{k-1}$ * 1.5) - 1

(la funzione ceil(x) indica il valore di x arrotondato all'intero superiore)

semplificando $n_k$ = $ceil(n_{k-1}$ * 1.5) - 1 possiamo approssimare C(n)

$n_k$ ≈ $n_{k-1}$ * 1.5 $n_k$ ≈ 1.5 * 1.5 * ... = $1.5^k$ k ≈ $log_{1.5}$ $n_k$

e semplificando molto possiamo farla valere per ogni valore di n, togliendo gli scalini

k ≈ $log_{1.5}$ n C = $3^k$ ≈ $3^{log1.5n}$ $log_3$ C ≈ $log_{1.5}n$ ln C / ln 3 ≈ ln n / ln 1.5 ln C ≈ ln n * (ln 3 / ln 1.5) ln C ≈ ln $(n^{(ln3/ln1.5)})$ C ≈ $n^{(ln3/ln1.5)}$

da cui C(n) ≈ $n^{2.71}$

La semplificazione produce una approssimazione abbastanza grossolana per situazioni non al limite: a titolo indicativo nell'intervallo n = 475...711 il valore reale C = $3^{15}$ è solo l'80%...27% della stima $n^{2.71}.$

### Analisi degli scambi

Qui l'analisi è semplice. Da un semplice esame dei valori prodotti dal calcolo di tutti i casi possibili si può constatare che S(n) = n * (n - 1) / 2 e il caso medio è esattamente la metà.

