[C] Ordinamento di tre vettori senza instanziarne un quarto
Salve a tutti
sono nuovo del forum ma non vi nascondo che spesso mi sono ritrovato a darci un occhio per varie materie.
Dopodomani ho l'esame di informatica e fortunatamente mi sento abbastanza preparato, però c'è un esercizio che mi toglie l'anima da ieri sera e non sono capace di capire come si può svolgere.
In pratica l'esercizio chiede di acquisire 3 vettori di grandezza diversa, poi ne rikiede l'ordinamento tramite selection sort nell'ipotesi in cui non sia possibile instanziare un quarto vettore. Infine l'esercizio chiede di memorizzare gli elementi dei tre vettori ordinati in un file e senza ripetizioni.
Vabbe sull'acquisizione nulla da dire, cosi come anche l'inserimento nel file ma
COME FACCIO IL SELECTION SORT SU TRE VETTORI SENZA UTILIZZARNE UN QUARTO?
cavolo ci sto sbattendo la testa da ieri e mi sono anche avvicinato per certi versi ma poi m perdo...avrei una mezza idea d come impostare il tutto infatti ma il problema è ke nel momento in cui dovrei pssare al confronto riguardante elementi del primo vettore con elementi del secondo o del terzo mi perdo di brutto
sono nuovo del forum ma non vi nascondo che spesso mi sono ritrovato a darci un occhio per varie materie.
Dopodomani ho l'esame di informatica e fortunatamente mi sento abbastanza preparato, però c'è un esercizio che mi toglie l'anima da ieri sera e non sono capace di capire come si può svolgere.
In pratica l'esercizio chiede di acquisire 3 vettori di grandezza diversa, poi ne rikiede l'ordinamento tramite selection sort nell'ipotesi in cui non sia possibile instanziare un quarto vettore. Infine l'esercizio chiede di memorizzare gli elementi dei tre vettori ordinati in un file e senza ripetizioni.
Vabbe sull'acquisizione nulla da dire, cosi come anche l'inserimento nel file ma
COME FACCIO IL SELECTION SORT SU TRE VETTORI SENZA UTILIZZARNE UN QUARTO?
cavolo ci sto sbattendo la testa da ieri e mi sono anche avvicinato per certi versi ma poi m perdo...avrei una mezza idea d come impostare il tutto infatti ma il problema è ke nel momento in cui dovrei pssare al confronto riguardante elementi del primo vettore con elementi del secondo o del terzo mi perdo di brutto
Risposte
Hai mai visto il merge sort? L'idea è in un certo senso simile. Ordini prima di tutto ogni array separatamente e poi utilizzi una specie di "merge" per scrivere i dati su file. Devi cioè scorrere i tre array in contemporanea, scrivendo su file il più piccolo tra gli elementi dei 3 array che stai considerando.
... facendo attenzione a "saltare" eventuali ripetizioni.
First of all: grazie per le risposte.
No, non abbiamo trattato il merge sort al corso ma in effetti ci avevo pensato all'ordinarli prima separatamente però ossessionato dall'idea di fare un select sort gigantesco per tutti e tre mi ero autoconvinto che la cosa fosse stupida. In più oggi non ho avuto la possibilità di utilizzare il pc (scrivo da un iphone) per vari problemi quindi non potevo neanche buttarmici...
Domani mattina provo e vi faccio sapere come va.
No, non abbiamo trattato il merge sort al corso ma in effetti ci avevo pensato all'ordinarli prima separatamente però ossessionato dall'idea di fare un select sort gigantesco per tutti e tre mi ero autoconvinto che la cosa fosse stupida. In più oggi non ho avuto la possibilità di utilizzare il pc (scrivo da un iphone) per vari problemi quindi non potevo neanche buttarmici...
Domani mattina provo e vi faccio sapere come va.
Ripensandoci, il selection sort può anche essere implementato sui 3 array. Ad ogni turno devi semplicemente trovare il minimo tra gli elementi dei 3 array che ti mancano. Volendo si potrebbe anche scrivere una funzione per lavorare sui 3 array come se fossero uno solo. Non ho idea di quale soluzione avesse in mente il tuo professore.
Guarda dalla traccia sembra che lui voglia un select sui tre array trattandoli come se fossero uno solo...il problema è ke provndoci e riprovandoci mi esce un immenso ciclo for con altri for e una marea di if niificati....
Alla partenza infatti mi sembra possibile...poi scrivendolo mi rendo conto di una serie di cose ke vanno trattate e adeguate volta per volta e ke nn si riescono a "far girare" come si vuole
Alla partenza infatti mi sembra possibile...poi scrivendolo mi rendo conto di una serie di cose ke vanno trattate e adeguate volta per volta e ke nn si riescono a "far girare" come si vuole
Sostanzialmente io ci ragiono cosi:
un for (I=0;I<(riempimento1+riempimento2+riempimento3);I++)
poi all'interno una serie di if, xkè se I è >=riemp1 devo usare un altro indice J=0 dato ke devo iniziare a "scalare" il secondo vettore
poi un altro if per I>=riemp2, anke qui servirà un terzo indice K=0 per iniziare il terzo vettore.
Poi mi blocco, ripenso al primo if e m rendo conto ke non deve essere I>=riemp1, ma questo if va spaccato in due xkè se I==riemp1 allora J=0, mentre se I>riemp1 e I
E questo per quello ke riguarda solo "la prima parte", ovvero senza calcolare il secondo for in cui metto tutti gli elementi a confronto con l'elemento "attuale" del for precedente...
Insomma io a questo punto già mi sono mezzo perso
un for (I=0;I<(riempimento1+riempimento2+riempimento3);I++)
poi all'interno una serie di if, xkè se I è >=riemp1 devo usare un altro indice J=0 dato ke devo iniziare a "scalare" il secondo vettore
poi un altro if per I>=riemp2, anke qui servirà un terzo indice K=0 per iniziare il terzo vettore.
Poi mi blocco, ripenso al primo if e m rendo conto ke non deve essere I>=riemp1, ma questo if va spaccato in due xkè se I==riemp1 allora J=0, mentre se I>riemp1 e I
E questo per quello ke riguarda solo "la prima parte", ovvero senza calcolare il secondo for in cui metto tutti gli elementi a confronto con l'elemento "attuale" del for precedente...
Insomma io a questo punto già mi sono mezzo perso
Potresti scrivere una funzione di supporto che dati i 3 array, le loro dimensioni e un indice ti restituisce il puntatore a questo elemento. In questo modo dovrebbe essere sufficiente sostituire questa funzione a a nel codice di un selection sort e hai risolto il tuo problema. Pensavo a qualcosa come
Un altro metodo è quello di fare un ciclo esterno in cui iteri sugli array e uno interno in cui iteri su tutti i suoi elementi. In questo modo è più facile stabilire l'indice attuale che devi utilizzare. Sarebbero però più facile se le dimensioni degli array e dei puntatori ad essi fossero memorizzati in un array.
int *fun(int *a1, int n1, int *a2, int n2, int *a3, int n3, int i)
{
if (i < n1) {
return a1 + i;
} else if ((i -= n1) < n2) {
return a2 + i;
} else if ((i -= n2) < n3) {
return a3 + i;
}
}
Un altro metodo è quello di fare un ciclo esterno in cui iteri sugli array e uno interno in cui iteri su tutti i suoi elementi. In questo modo è più facile stabilire l'indice attuale che devi utilizzare. Sarebbero però più facile se le dimensioni degli array e dei puntatori ad essi fossero memorizzati in un array.
anche se in ritardo, wikipedia sotto la voce selection sort ti mostra come si puo fare tutto in place (ovvero senza usare memoria aggiuntiva)
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo