|
|
|
Třídění
přetřásáním (shakesort)
je vylepšením algoritmu bublinkového
třídění. Tříděnou posloupnost procházíme střídavě od prvního k
poslednímu a naopak, nejmenší a největší prvek se dostanou na své místo
ihned atd. Jeho algoritmus můžeme v
Pascalu zapsat ve tvaru následující procedury: procedure
Třesení; var
j,k,l,r : index; x:
prvek; begin l := 2; r
:= n; k := n; repeat for
j := r downto l do
{průchod od konce} if
a[j-1].klíč > a[j].klíč then begin x
:= a[j-1];
{výměna} a[j-1]
:= a[j]; a[j] := x; k
:= j
{index poslední výměny} end; l
:= k+1;
{příště procházíme jen od l} for
j := l to r do
if a[j-1].klíč > a[j].klíč
then begin x
:= a[j-1];
{výměna} a[j-1]
:= a[j]; a[j] := x; k
:= j
{index poslední výměny} end; r
:= k-1;
{příště procházíme jen od r} until l
> r
{když se l a r se setkají, konec} end
{Třesení} Analýza třídění přetřásáním
Je-li tříděné
pole již uspořádané, bude mít proměnná k
po skončení prvního cyklu for
hodnotu n, neboť podmínka v příkazu if
nebude splněna ani jednou. Proměnná
l tím získá hodnotu n+1 a tělo
druhého cyklu for se neprovede již
ani jednou. Proměnná r pak dostane
hodnotu n-1, cyklus repeat skončí. Nejmenší počet porovnání proto bude Cmin = n - 1. Pokud jde o průměrný
počet výměn, D. Knuth ukázal, že je roven
kde r je jistá konstanta. Počet výměn zůstává u třídění přetřásáním stejný jako u bublinkového třídění. To znamená, že ve většině případů nebudou mít uvedená vylepšení metody bublinkového třídění velký význam.
|
|
|
