# 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à.