Trippel sort

Da Wikipedia, l'enciclopedia libera.
Trippel sort
Sorting stoogesort anim.gif
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[modifica | modifica sorgente]

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)[modifica | modifica sorgente]

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 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[modifica | modifica sorgente]

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[modifica | modifica sorgente]

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)[modifica | modifica sorgente]

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[modifica | modifica sorgente]

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[modifica | modifica sorgente]

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[modifica | modifica sorgente]

  • (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[modifica | modifica sorgente]