[C++] mi date un suggerimento per esercizio sui vettori?

[milu]

ciao a tutti..
vorrei un suggerimento..
devo scrivere un programma che inserisca elementi in un vettore già ordinato..
se ad esempio il vettore è composto dai numeri 4 6 8 9, aggiungendo 3 e 5, avrò
3 4 5 6 8 9
è meglio che creo due vettori che poi vado a fondere in un terzo e ordino quest'ultimo,o posso fare diversamente?
grazie!!

[oregon]

Originariamente inviato da milu
ciao a tutti..
vorrei un suggerimento..

Non sai che questo forum ha un regolamento?

[MItaly]

Puoi seguire più approcci.
Supponendo che il vettore già ordinato sia già grande a sufficienza per contenere tutti gli elementi:
- se tu hai già pronta una funzione di ordinamento, il metodo più immediato e "ignorante" può essere accodare i due elementi e ordinare il vettore così ottenuto; le performance quindi sono O(n log n) nel numero totale di elementi (in realtà per alcuni algoritmi peggio, ad esempio il quicksort, con un vettore quasi completamente ordinato, peggiora di molto le performance).
- un metodo più furbo può invece sfruttare il fatto che il primo vettore è già ordinato, e che il secondo (se è di pochi elementi) si ordina molto in fretta. A questo punto, ti muovi con tre indici (o puntatori): un indice di scrittura sul vettore finale, uno di lettura su ciascuno dei due vettori. L'indice di scrittura parte dall'ultimo slot del vettore di destinazione, e i due indici di lettura partono nell'ultima posizione valida dei due vettori di input. Ad ogni iterazione, controlli quale elemento di quelli puntati dai due indici di lettura è il minore; questo verrà copiato nella posizione indicata dall'indice di scrittura, e il corrispondente indice (oltre a quello di scrittura) viene spostato indietro di un posto. Supponendo che il secondo vettore sia già ordinato, questa fase di merge è O(n) nel numero totale degli elementi.

Se invece non c'è spazio nel vettore di destinazione, puoi fare la stessa cosa usando un terzo vettore, ma in questo caso nulla ti impedisce di lavorare "dal davanti" dei vettori (il lavorare all'indietro è reso necessario per lavorare inplace sul secondo vettore); quello appena descritto comunque è detto "algoritmo di merge".

---

In ogni caso, dovresti chiarire se si tratta di una questione puramente algoritmica, oppure, se si parla di codice, come già sai devi specificare il linguaggio di riferimento (anche nel titolo).

[milu]

scusatemi volevo un consiglio..non voglio codici pronti..devo scriverlo io e volevo un suggerimento..
grazie comunque..

[oregon]

Originariamente inviato da milu
devo scriverlo io

Adesso hai aggiunto il linguaggio, ma dovresti indicarlo *sempre* sin dall'inizio perché è importante ai fini della risposta.

[milu]

hai ragione..
sorry