Come ordinare un vettore nel linguaggio C

In questo script ordino un vettore tramite una funzione basata sull'algoritmo di ordinamento Bubble Sort.

1. #include <stdio.h>
2. void ordinamento(int v[], int n) {
3. int scambio,i,k;
4. do {
5. scambio = 0;
6. for (i=0; i<n-1; i++) {
7. if (v[i]>v[i+1]) {
8. k=v[i+1];
9. v[i+1]=v[i];
10. v[i]=k;
11. scambio = 1;
12. }
13. }
14. printf("\n");
15. for (i=0;i<n;i++) {
16. printf(" %d ",v[i]);
17. }
18. } while(scambio==1);
19. return;
20. }
21. int main()
22. {
23. int v[]={11,2,33,24,15,36,17,8,19,20};
24. ordinamento(v,10);
25. }

Nel programma definisco una funzione ordina() per fare l'ordinamento (sort) di un vettore.

La funzione prende in input un vettore e il numero degli elementi del vettore.

Come funziona

Nella riga 23 della funzione main() dichiaro e definisco un vettore composto da 10 numeri interi.

La sequenza dei numeri non è ordinata.

int v[]={11,2,33,24,15,36,17,8,19,20};

Nella riga 24 richiamo la funzione ordinamento() passandogli come parametri il vettore v e il numero degli elementi che contiene.

ordinamento(v,10);

Nella riga 2 la funzione ordinamento() riceve i parametri usando le variabili locali v e n.

void ordinamento(int v[], int n) {

Nel caso dei vettori il passaggio avviene per riferimento. Pertanto, qualsiasi modifica al vettore apportata dalla funzione avviene direttamente sul vettore originale.

La funzione si basa sull'algoritmo di ordinamento Bubble Sort.

Nelle righe da 4 a 18 un ciclo do while legge il vettore finché non si verifica nessuno scambio.

4 do {
5 scambio = 0;
...
18 } while(scambio==1);

La variabile scambio è 1 se il programma ha modificato il vettore nell'ultima iterazione, viceversa è 0 se non è stata apportata nessuna variazione.

All'interno del ciclo do while inserisco un ciclo incondizionato for per leggere in sequenza gli elementi del vettore.

6 for (i=0; i<n-1; i++) {
7 if (v[i]>v[i+1]) {
8 k=v[i+1];
9 v[i+1]=v[i];
10 v[i]=k;
11 scambio = 1;
12 }
13 }

Ogni volta che il programma legge un elemento del vettore lo confronta con l'elemento immediatamente successivo (riga 7).

• Se il valore dell'elemento corrente v[i] è maggiore di quello successivo v[i+1], scambia gli elementi di posto (righe 8-10) e assegna 1 alla variabile scambio per segnalare la variazione (riga 11).
• Se il valore dell'elemento corrente v[i] non è maggiore di quello successivo v[i+1], il ciclo for termina l'iterazione e legge l'elemento successivo del vettore.

Il ciclo for termina quando raggiunge il penultimo elemento del vettore.

A questo punto il controllo torna al ciclo più esterno (do while) che verifica il contenuto della variabile scambio (riga 18).

• Se scambio = 1 il ciclo esterno compie un'altra iterazione perché il vettore è stato modificato di recente.
• Se scambio = 0 il ciclo esterno conclude le iterazioni perché l'ultima iterazione non ha apportato nessuna modifica al vettore. La funzione ordinamento() restituisce il controllo alla funzione main() del programma.

Durante l'elaborazione il programma stampa il contenuto del vettore al termine di ogni ciclo (righe 14-17).

In questo modo posso vedere al termine di ogni ciclo interno le variazioni nella sequenza degli elementi.

2 11 24 15 33 17 8 19 20 36
2 11 15 24 17 8 19 20 33 36
2 11 15 17 8 19 20 24 33 36
2 11 15 8 17 19 20 24 33 36
2 11 8 15 17 19 20 24 33 36
2 8 11 15 17 19 20 24 33 36
2 8 11 15 17 19 20 24 33 36

Gli elementi del vettore sono ordinati in ordine crescente

Complessivamente il programma itera ha iterato 7 volte la do while per ordinare gli elementi del vettore.

Questo algoritmo di ordinamento è molto semplice da realizzare ma poco efficiente, perché la complessità computazionale cresce con il numero degli elementi del vettore.

Nota. Per ordinare gli elementi in ordine decrescente devo soltanto modificare la relazione d'ordine alla riga 7 da maggiore if (v[i]>v[i+1]) a minore if (v[i]<v[i+1]). Questa modifica mi permette di ottenere l'ordinamento decrescente del vettore.

E così via.