Oggetto dell'analisi - Algoritmo risolutivo

informatica

Oggetto dell'analisi:

ordinamento di liste

Algoritmo risolutivo

Dati in ingresso : un puntatore ad una lista non in ordine.

Dati in uscita : nessuno. Il risultato è un 545c28f a lista ordinata, ma questa non è il valore di ritorno.

Variabili di lavoro

ptr2 viene utilizzato per individuare l'elemento della lista che viene analizzato  di volta in volta.

com viene utilizzata per effettuare scambi di indirizzi.

changes indica se sono stati effettuati degli scambi all'interno della lista.

procedure ordina(var ptr : puntatore);

var ptr2,com:puntatore;

changes:boolean;

begin

if ptr <> nil then

repeat

ptr2:=ptr;

changes:=false;

while ptr2.pointer <> nil do

if ptr2.pointer^.info > ptr2^.info then

begin

com:=ptr2;

ptr2:=ptr2^.pointer;

ptr2^.pointer:=com;

changes:=true;

end;

until not changes;

end.

L'algoritmo lavora in questo modo:

1- controlla se la lista non sia vuota. In caso affermativo non effettua modifiche.

2- per ogni elemento della lista, controlla se l'elemento successivo sia maggiore di questo. In caso affermativo, avviene lo scambio di posizione.

3- ripete il punto 2 fino al momento in cui non sono avvenuti scambi.

Considerazioni

Il punto di forza di questo sistema di ordinamento sta nella sua semplicità, ma comunque risente della sua lentezza che se applicato a liste di grandi dimensioni diventa problematica.