Trippel sort
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. DescrizioneL'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.
Analisi dei confrontiSi 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 per n ≥ nk , dove (la funzione ceil(x) indica il valore di x arrotondato all'intero superiore) n=2 ↔ C=1 (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 scambiS(n) = (n - 1) * (n - 2) / 2 + 1 - Δk , per n ≥ nk. Δ1 = 1 per n1 = 8 n=2 ↔ S=1 , Smedio=0.50 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.
Analisi dei confrontiPer 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: n=2 ↔ C=1 da cui si ricava la relazione Ck = 3k, per n ≥ nk dove (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 e semplificando molto possiamo farla valere per ogni valore di n, togliendo gli scalini k ≈ log1.5 n 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 scambiQui 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
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Portal di Ensiklopedia Dunia
