Trippel sort

Da Wikipedia, l'enciclopedia libera.

Questa voce o una sua sezione non riporta le fonti e i riferimenti utilizzati per la redazione ed utili per verificare l'attendibilità e la correttezza dei contenuti. Se puoi, aiuta la voce inserendo le appropriate citazioni, e poi rimuovi questo avviso.
Nel caso in cui soltanto alcune circoscritte affermazioni siano mancanti di fonti, è più opportuno il template {{citazione necessaria}}

TrippelSort (conosciuto anche come StoogeSort) rientra nel gruppo dei peggiori algoritmi di ordinamento ed è per questo motivo poco conosciuto. L'algoritmo ha valore per scopi didattici ma non dovrebbe mai essere usato per ordinamenti veri e propri.

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

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

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

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

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

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

[modifica] 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à.

[modifica] Collegamenti esterni

www.sortieralgorithmen.de