Trippel sort
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 wikitesto]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 wikitesto]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 wikitesto]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 wikitesto]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 wikitesto]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 wikitesto]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 wikitesto]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 wikitesto]- (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 wikitesto]- (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.