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 log1.5 3.

sub TrippelSort(A() as <integer>, L as integer, R as integer) dim k,size as integer if A(L) > A(R) then Swap A, L, R end size = R - L + 1 if size >= 3 then k = size div 3 // divisione intera, arrotondato all'intero inferiore TrippelSort A, L, R - k TrippelSort A, L + k, R TrippelSort A, L, R - k end end

sub Swap(A() as <integer>, i as integer, j as integer) dim temp as <integer> temp = A(i) A(i) = A(j) A(j) = temp end

// Sostituire lo pseudotipo <integer> con quello desiderato.

Caratteristiche ricorsiva, in loco, non stabile, non parallelizzabileStrutture dati vettoriCasimiglioremediopeggioreMemoriaΩ(log n)Θ(log n)Ο(log n)TempoΩ(n2.71)Θ(n2.71)Ο(n2.71)Confronti C(n) = ∑i=0...k 3k , per n ≥ nkScambi0≅S(n) / 2S(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:

C0 = 1 Ck = Ck-1 * 3 + 1 cioè Ck = ∑i=0...k 3k

per n ≥ nk , dove n0 = 2 n1 = 3 nk = ceil(nk-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

3k+3k-1+... con 3k allora C(n) ≈ n2.71 come per la variante 2.

Analisi degli scambi S(n) = (n - 1) * (n - 2) / 2 + 1 - Δk , per n ≥ nk.

Δ1 = 1 per n1 = 8 Δ2 = ? per n2 = ? …

n=2 ↔ S=1 , Smedio=0.50 n=3 ↔ S=2 , Smedio=1.17 n=4 ↔ S=4 , Smedio=2.17 n=5 ↔ S=7 , Smedio=3.57 n=6 ↔ S=11 , Smedio=5.60 n=7 ↔ S=16 , Smedio=7.99 n=8 ↔ S=21 , Smedio=10.63 n=9 ↔ S=28 , Smedio=14.14 n=10 ↔ S=36 , Smedio=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.

sub TrippelSort(A() as <integer>, L as integer, R as integer) dim k,size as integer size = R - L + 1 if size >= 3 then k = size div 3 // divisione intera, arrotondato all'intero inferiore TrippelSort A, L, R - k TrippelSort A, L + k, R TrippelSort A, L, R - k elseif A(L) > A(R) then Swap A, L, R end end

sub Swap(A() as <integer>, i as integer, j as integer) dim temp as <integer> temp = A(i) A(i) = A(j) A(j) = temp end

// Sostituire lo pseudotipo <integer> con quello desiderato.

Caratteristiche ricorsiva, in loco, stabile, non parallelizzabileStrutture dati vettoriCasimiglioremediopeggioreMemoriaΩ(log n)Θ(log n)Ο(log n)TempoΩ(n2.71)Θ(n2.71)Ο(n2.71)Confronti C(n) = 3k, per n ≥ nkScambi0n * (n - 1) / 4n * (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 3k 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=32 n≥5 ↔ C=33 n≥7 ↔ C=34 n≥10 ↔ C=35 …

da cui si ricava la relazione

Ck = 3k, per n ≥ nk

dove n0 = 2 n1 = 3 nk = ceil(nk-1 * 1.5) - 1

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

semplificando nk = ceil(nk-1 * 1.5) - 1 possiamo approssimare C(n)

nk ≈ nk-1 * 1.5 nk ≈ 1.5 * 1.5 * ... = 1.5k k ≈ log1.5 nk

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

k ≈ log1.5 n C = 3k ≈ 3log1.5 n log3 C ≈ log1.5n ln C / ln 3 ≈ ln n / ln 1.5 ln C ≈ ln n * (ln 3 / ln 1.5) ln C ≈ ln (n(ln 3 / ln 1.5)) C ≈ n(ln 3 / ln 1.5)

da cui C(n) ≈ n2.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 = 315 è solo l'80%...27% della stima n2.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à.

Bibliografia

Collegamenti esterni

Categoria:Algoritmi di ordinamento