Ordinamento (linguaggio C)

[Luigi97]

Salve,
Stavo leggendo come creare un algoritmo per ordinare gli elementi di un vettore, ho deciso di aprire questa discussione perché non ho capito una cosa: perché per far si che tra un "vettore[x]" e un "vettore[y]" ci sia uno scambio di valori, c'è bisogno di una terza variabile?
Per esempio (guardate sotto il commento "ordinamento del vettore in ordine crescente"):

Codice: Seleziona tutto

#include <stdio.h>

/*ordinare gli elementi di un vettore in ordine crescente*/

#define MAX_ELE 99 /*limite del vettore*/

main(void) {
int x, y, n, scambio;
int vettore[MAX_ELE];

do {
printf("Stabilisci la grandezza del vettore (massimo %d): ", MAX_ELE);
scanf("%d", &n);
}while(n<1 || n>MAX_ELE);

printf("\n");

for(x=0; x<n; x++) {
printf("Inserisci il valore in posizione vettore[%2d]:  ", x);
scanf("%d", &vettore[x]);   
}

/*ordinamento del vettore in ordine crescente*/
for(x=0; x<n; x++) {
for(y=0; y<n; y++) {
if(vettore[x]<vettore[y]) {
scambio = vettore[y];   
vettore[y] = vettore[x];
vettore[x] = scambio;   
}   
}   
}

/*visualizzazione*/
printf("\nOrdinamento del vettore in ordine crescente");
for(x=0; x<n; x++) {
printf("\nPosizione vettore[%2d] = %2d", x, vettore[x]);
}

printf("\n");



    return 0;
}


Perché per fare in modo che vettore[x] assuma il valore di vettore[y] c'è bisogno di una variabile di appoggio?
All'interno dei cicli for, anziché scrivere

Codice: Seleziona tutto

scambio = vettore[y];   
vettore[y] = vettore[x];
vettore[x] = scambio;


, perché non si può fare direttamente così

Codice: Seleziona tutto

vettore[y] = vettore[x]
vettore[x] = vettore[y]


?

Se si esegue il ciclo senza la variabile di appoggio le posizioni (posizioni?) dei vettori assumono tutte uno stesso valore (il più minore o il più maggiore, dipende da come si imposta il ciclo), però non ho capito perché...

Comunque l'algoritmo è semplice, il pdf mi proponeva un certo algoritmo chiamato "bubblesort", però non ci ho capito molto... tuttavia da esso ne ho tratto spunto e ne è uscito fuori quello che ho postato sopra.
In pratica funziona così: ci sono due cicli for. Il ciclo esterno e il ciclo interno vengono ripetuti per uno stesso valore chiamato "n".
All'avvio dei cicli, "x" assume il valore 0 dopodiché inizia il ciclo interno e, ogni volta che il ciclo interno termina, viene incrementato il valore della variabile "x" del ciclo più esterno. I cicli termineranno fin quando "x" non sarà più minore di "n".
Detto ciò, facciamo che "n" valga 5 e che nel vettore inseriamo i seguenti valori: 4,5,6,7,2.
All'avvio dei cicli, avremo che vettore[x] = 4, mentre vettore[y] sarà prima 4, poi 5, poi, 6, poi 7 e infine 2.
L'"if" ci dice che se vettore[x]<vettore[y] allora avviene lo scambio di valori.
Avremo che... per esempio, la prima interazione sarà così:
vettore[0]di_x (che contiene 4) si confronterà con vettore[0]di_y (che anch'esso contiene 4). Poiché sono uguali non ci sarà nessun scambio. Dopodiché, "y" (che fa parte del ciclo interno) prosegue con l'interazione e diventa 1. Nel vettore[1] abbiamo come valore 5. Quindi, vettore[0]di_x, essendo minore di 5, scambierà il proprio valore con vettore[1]di_y. Dopo ciò, avremo che vettore[0]di_x avrà il valore di 5 mentre vettore[1]di_y avrà il valore di 4.
"y" prosegue con l'incremento e assume il valore di 2. Vettore[2] ha il valore di di 6. vettore[0]di_x (che adesso vale 5) è minore di vettore[2]di_y. Si effettua un altro scambio e avremo che vettore[0]di_x = 6, mentre vettore[2]di_y = 5. E così via...
Quando i due cicli termineranno il primo avvio, il vettore avrà i valori nell'ordine di: 7,4,5,6,2. In pratica, nel primo avvio, il numero maggiore se lo porta in cima, per poi scalarlo man mano ad ogni ripetizione, mentre i valori minori saliranno in alto.
Per esempio la seconda ripetizione termina con i valori del vettore ordinati così: 4,7,5,6,2. Il motivo spero di averlo saputo spiegare.
E' più facile da capire che spiegare...

Comunque però non credo che questo algoritmo vada bene. Il pdf parlava di algoritmi che interrompono i cicli for non appena i valori del vettore sono ordinati nella maniera desiderata. Con l'algoritmo sopracitato i cicli for devono per forza completare tutti gli incrementi (credo che approfondirò in seguito). Per adesso vorrei avere solo una risposta alla domanda sopracitata.

[DanteCpp]

Supponi di avere una bottiglia di vino nella mano destra e una di birra nella sinistra, riusciresti a scambiare la posizione delle bottiglie senza poggiarne una sul tavolo?

[rugweri]

perché non si può fare direttamente così

Codice: Seleziona tutto

vettore[y] = vettore[x]
vettore[x] = vettore[y]


Analizziamo insieme cosa quelle istruzioni dicono al programma di fare:

Supponiamo di avere i dati:

v1 = 1, 2, 3, 4, 5
y = 1
x = 0

Eseguiamo la prima istruzione: il risultato è

vettore[1] = vettore[0] -----------------> v1 = 1, 1, 3, 4, 5

Abbiamo spostato il primo elemento al secondo posto, ma abbiamo perso ogni traccia del contenuto originale della seconda cella!!
Questo vuol dire che, eseguendo subito dopo l'altra istruzione, otteniamo:

vettore[0] = vettore[1] -----------------> v1 = 1, 1, 3, 4, 5

Che non è quello che volevamo.

[Luigi97]

...
vettore[1] = vettore[0] -----------------> v1 = 1, 1, 3, 4, 5

Abbiamo spostato il primo elemento al secondo posto, ma abbiamo perso ogni traccia del contenuto originale della seconda cella!!

Hai ragione. Adesso è così ovvio che sia così che temo di aver mostrato non molta intelligenza.

Chiedo scusa al forum per la domanda elementare.

Grazie per la risposta, buona giornata a tutti.

[DanteCpp]

Porsi delle domande è sempre lecito.

[xyz]

La CPU è deterministica, ad ogni ciclo di clock ogni cella di memoria ha il suo unico dato e le istruzioni sono eseguite in sequenza, quindi le 2 istruzioni indicate per lo scambio di variabili non possono funzionare.

Esiste la possibilità di non usare una variabile di appoggio utilizzando 3 istruzioni in sequenza, si usa l'operatore XOR:

Codice: Seleziona tutto

vettore[x] ^= vettore[y];
vettore[y] ^= vettore[x];
vettore[x] ^= vettore[y];

o in forma più compatta in una sola riga (sono sempre 3 operazioni in sequenza):

Codice: Seleziona tutto

vettore[x] ^= vettore[y] ^= vettore[x] ^= vettore[y];

Per gli array comunque è consigliabile usare la variabile temporanea per lo scambio tra due elementi, il codice generato è di solito più efficiente.

[IlGuru]

Sono errori che si commettono più spesso di quanto tu non creda, specialmente lavorando con i puntatori.

[rugweri]

Esiste la possibilità di non usare una variabile di appoggio utilizzando 3 istruzioni in sequenza, si usa l'operatore XOR:

Codice: Seleziona tutto

vettore[x] ^= vettore[y];
vettore[y] ^= vettore[x];
vettore[x] ^= vettore[y];

Questa soluzione, pur non essendo il massimo per chiarezza e - come già notato - per efficienza (tant'è che in circa dieci anni di studio del linguaggio C l'ho usata forse due volte), è interessante... ma il nostro richiedente è sicuramente nella primavera della sua esperienza informatica, per cui mi permetto di integrare la proposta mostrando con un veloce esempio cosa fanno quelle istruzioni:

Poniamo che i due elementi da scambiare siano, in codifica binaria:

vettore[x] = 01001011
vettore[y] = 10011010

Come sappiamo, la disgiunzione esclusiva è vera se e solo se i due operandi hanno valori di verità diversi, per cui le tre istruzioni ci forniscono il risultato:

vettore[x] ^= vettore[y] --------------> vettore[x] = (01001011) XOR (10011010) = 11010001
vettore[y] ^= vettore[x]; --------------> vettore[y] = (10011010) XOR (11010001) = 01001011
vettore[x] ^= vettore[y]; --------------> vettore[x] = (11010001) XOR (01001011) = 10011010

Che è esattamente ciò che volevamo

[Luigi97]

Esiste la possibilità di non usare una variabile di appoggio utilizzando 3 istruzioni in sequenza, si usa l'operatore XOR:

Codice: Seleziona tutto

vettore[x] ^= vettore[y];
vettore[y] ^= vettore[x];
vettore[x] ^= vettore[y];

...il nostro richiedente è sicuramente nella primavera della sua esperienza informatica, per cui mi permetto di integrare la proposta mostrando con un veloce esempio cosa fanno quelle istruzioni:
...

Infatti non avevo capito perché funzionava... però adesso grazie alla tua spiegazione è tutto chiaro .

Comunque grazie a tutti ragazzi siete davvero molto gentili.