Page 1615 - Informatica dalla A a Z

Esercitazioni e Problemi (in C++)

Problema1: Ordinamento: data una sequenza di elementi, si vogliono ridistribuire gli stessi

in modo che, letti in sequenza, rispettino una relazione d’ordine.

Per esempio, se la sequenza fosse [10, 55, 5, 90, 17], il risultato dell’ordinamento dovrebbe
essere [5, 10, 17, 55, 90].

Sono stati messi a punto numerosi algoritmi per risolvere questa tipologia di problemi, al-
cuni dei quali anche molto sofisticati.

Uno tra i più semplici ed intuitivi può essere descritto informalmente nel modo seguente:

• Si legga da input la sequenza di dati (interi) e la si memorizzi nell’array “seq” di lun-
ghezza n.

• Si divida l’array “seq” in due parti contigue in modo che la prima, quella di sinistra,

sia ordinata in ordine crescente, si indichi con j l’indice del primo elemento della parte
destra dell’array: si noti che questo scopo può essere ottenuto immediatamente per qual-
siasi array scegliendo come parte sinistra il solo primo elemento (una sequenza di un solo

elemento è ovviamente sempre ordinata) e quindi la partizione desiderata può essere ot-
tenuta inizialmente semplicemente assegnando alla variabile j il valore 1 corrispondenete
al secondo elemento dell’array.

• Si noti poi che se invece la parte destra dell’array si riducesse ad una sequenza vuota

la parte sinistra consisterebbe nell’intero array ordinato. Si costruisce quindi un ciclo che
ad ogni iterazione sposta l’elemento seq[j] dalla posizione j-esima all’interno della parte
sinistra, la cui lunghezza quindi cresce di un’unità, nella posizione adatta affinché la parte

sinistra si mantenga ordinata.

• Per ottenere questo effetto si memorizzi il valore di seq[j] in una variabile tempora-
nea temp; quindi si facciano scorrere gli elementi della parte sinistra dell’array maggiori di
temp di una posizione a destra finché non si trova il primo di valore <= temp: il valore di

temp viene quindi memorizzato alla sua immediata destra. Si noti che come caso partico-
lare seq[j], e quindi temp, potrebbe essere <= di tutti gli elementi della parte sinistra

dell’array.

Si codifichi mediante il nucleo semplificato del C l’algoritmo informalmente descritto so-
pra.

Soluzione:

#include <stdio.h>

1611