Tags:
create new tag
view all tags

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

-- AndreaSterbini - 26 Mar 2002

Edit | Attach | Watch | Print version | History: r3 < r2 < r1 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r3 - 2002-03-29 - AndreaSterbini






 
Questo sito usa cookies, usandolo ne accettate la presenza. (CookiePolicy)
Torna al Dipartimento di Informatica
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2022 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback