Quick Sort

Si crei un vettore 'packed' (impacchettato) di numeri ciascuno lungo 13 bit nel formato a complemento a 2:

• il primo occupa un byte più i primi 5 bit del byte successivo
• il secondo occupa i rimanenti 3 bit più 8 del byte successivo più 2 del seguente
• così via ...

Esempio

Si spacchetti il vettore in un vettore di half word estendendo il segno.

Si ordini il vettore di half word usando l'algoritmo quick-sort (ricorsivo).

Algoritmo quick-sort

• se il vettore è formato da 0 o 1 elemento allora è già ordinato
• si scelga un elemento 'pivot' a caso del vettore (ad esempio il primo)
• si confronti l'elemento con ciascun elemento del vettore, ponendo prima di esso tutti gli elementi minori e dopo di esso tutti gli elementi uguali o maggiori (in questo processo l'elemento scelto verrà spostato nella sua posizione finale corretta)
• si usi ricorsivamente l'algoritmo quick-sort sui due vettori formati dagli elementi PRIMA e DOPO il 'pivot' per ordinarli

Svolgimento

• si scriva una procedura di input per inserire gli elementi del vettore 'packed' (al massimo 100)
• si scriva una procedura che spacchetta il vettore 'packed' costruendo il vettore di half-word
• si scriva una procedura di output che stampi gli elementi del vettore di half-word
• si scriva una procedura ricorsiva che ordina un vettore di half usando l'algoritmo quick-sort
• si scriva il programma che:
  • chiede gli elementi del vettore e li impacchetta nel vettore
  • spacchetta il vettore costruendo il vettore di half
  • ordina gli elementi del vettore di half
  • stampa il vettore risultato

Suggerimento: si passino alla procedura quick-sort i due indirizzi del primo e dell'ultimo elemento

Per porre domande sul testo dell'esercizio editate DomandeSecondoProgetto2002

-- AndreaSterbini - 26 Mar 2002

• Set ALLOWTOPICCHANGE = DocentiArcGroup