3° Anno TEORIA 9. Tipi di dato strutturato: vettori e record | Page 21

8 : I dati e la loro struttura nella programmazione ( ARRAY , MATRICI , RECORD ) Vers . 8.2 – Settembre 2022

n . b . ogni volta si resetta l ’ indicatore degli scambi effettuati i � 1 ( i = 1 ) TEST PER ( i ≤ sup-1 ) ossia ( 1 ≤ 0 ) FALSO Ciclo PER non eseguito NO SCANSIONE

TEST MENTRE ( continua = VERO ) ossia ( FALSO = VERO )? N . B . Il vettore ora risulterà perfettamente ordinato

FALSO STOP

1 2 3 4

4 10 19 25

LE DUE STRATEGIE DI ORDINAMENTO A CONFRONTO

Se confrontiamo , nel caso del vettore proposto , i due algoritmi equivalenti di ordinamento tra di loro ci accorgeremo che essi hanno compiuto esattamente lo stesso numero di scansioni e di passi per giungere al medesimo scopo e quindi sembrerebbero perfettamente equivalenti .

ATTENZIONE : NON E SEMPRE COSI ’!

Basterebbe ripetere per esercizio le scansioni / confronti che i due algoritmi di ordinamento impiegano per ordinare in senso CRESCENTE il seguente altro vettore v di interi di dimensione quattro ( n = 4 ):

per accorgersi della maggiore efficienza dell ’ ordinamento BUBBLE SORT rispetto all ’ ordinamento INGENUO , soprattutto per i vettori che mostrano valori poco disordinati ( o in altri termini più ordinati ) rispetto al criterio di ordinamento richiesto . In questoi caso infatti :

- l ’ ordinamento INGENUO otterrà l ’ ordinamento in senso CRESCENTE del vettore effettuando comunque n-1 scansioni ( con la prima scansione che effettuerà esatamente n-1 confronti );

- l ’ ordinamento a bolle o BUBBLE-SORT otterrà l ’ ordinamento in senso CRESCENTE del vettore effettuando 2 sole scansioni ( grazie al poco disordine dei valori rispetto al criterio fissato ).

Quindi ciò che fa la differenza in questo caso non è solo il numero iniziale degli elementi del vettore ( dimensione ), ma soprattutto la loro disposizione iniziale ( ossia come tali valori sono distribuiti ).

Autore : Rio Chierego ( email : riochierego @ libero . it - sito web : www . riochierego . it ) Pag . 21