SecondoProgetto2002 < Architetture2/MZ

---++ 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
| *numeri:* | 13 bit ||||||||||||| 13 bit ||||||||||||| 13 bit |||||||||||||
|           | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 0 |
| *bytes:*  | 8 bit |||||||| 8 bit |||||||| 8 bit |||||||| 8 bit |||||||| 8 bit ||||||||

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

-- Users.AndreaSterbini - 26 Mar 2002

   * Set ALLOWTOPICCHANGE = Users.DocentiArcGroup
This topic: Architetture2/MZ > DateEScadenze > SecondoProgetto2002
Topic revision: r3 - 2002-03-29 - AndreaSterbini