Trippel sort

Trippel sort
Visualizzazione del Trippel sort
Classe	Algoritmo di ordinamento
Struttura dati	Array
Caso peggiore temporalmente	O(nlog(3)/log(1.5))
Caso peggiore spazialmente	O(n)
Ottimale	No

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.

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 parallelizzabile
Strutture dati	vettori
Casi	migliore	medio	peggiore
Memoria	Ω(log n)	Θ(log n)	Ο(log n)
Tempo	Ω(n2.71)	Θ(n2.71)	Ο(n2.71)
Confronti	C(n) = ∑i=0...k 3k , per n ≥ nk
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₀ = 1
C_k = C_k-1 * 3 + 1
cioè C_k = ∑_i=0...k 3^k

per n ≥ n_k , dove
n₀ = 2
n₁ = 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 per n₁ = 8
Δ₂ = ? per n₂ = ?
…

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.

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 parallelizzabile
Strutture dati	vettori
Casi	migliore	medio	peggiore
Memoria	Ω(log n)	Θ(log n)	Ο(log n)
Tempo	Ω(n2.71)	Θ(n2.71)	Ο(n2.71)
Confronti	C(n) = 3k, per n ≥ nk
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²
n≥5 ↔ C=3³
n≥7 ↔ C=3⁴
n≥10 ↔ C=3⁵
…

da cui si ricava la relazione

C_k = 3^k, per n ≥ n_k

dove
n₀ = 2
n₁ = 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^{log_1.5 n}
log₃ C ≈ log_1.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) ≈ 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¹⁵ è 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à.

Bibliografia

• (EN) Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein, Problems 7-3: Stooge sort, in Introduction to Algorithms, Second Edition, The MIT Press, 2001.

Collegamenti esterni

• (EN) Paul E. Black, stooge sort, su Dictionary of Algorithms and Data Structures, U.S. National Institute of Standards and Technology, 17 dicembre 2004. URL consultato l'8 settembre 2012 (archiviato dall'url originale il 22 settembre 2012).
• (EN) Everything2.com – Trippel sort, su everything2.com.
• (EN) Algoritmi di ordinamento (incluso il Trippel sort), su cg.scs.carleton.ca.