Nel frammento di codice sottostante viene presentato l’algoritmo di ordinamento Merge Sort. L’algoritmo Merge Sort è un algoritmo che sfrutta le tecniche di Ricorsione e di Divide et Impera per ordinare un vettore di elementi.
#include <stdlib.h> #include <stdio.h> #include <string.h> #include <limits.h> void stampa(int *a, int n); void mergeSort(int *a, int n); int main(void) { int a[10] = {5, 1, 3, 99, 45, 63, 21, 34, 0, 84}; // elementi da ordinare int n = 10; // numero di elementi stampa(a, n); mergeSort(a, n); stampa(a, n); return 1; } // stampo tutti i valori presenti nel vettore void stampa(int *a, int n) { int i; for(i=0; i<n; i++) printf("%d ", a[i]); printf("\n"); } // passo alla funzione il puntatore al vettore da ordinare e la sua dimensione void mergeSort(int *a, int n) { int *a1 = NULL, *a2 = NULL; int a1_n, a2_n; int i, x, y; // se il vettore è formato un solo elemento allora è già ordinato, altrimenti procedo if(n == 1) return; // calcolo le nuove dimensione dei sotto-vettori di a a1_n = n/2; a2_n = n/2; if(n%2!=0) { // se n è dispari a1_n++; //ceil } // creo i nuovi sotto-vettori a1 = realloc(a1, a1_n*sizeof(int)); a2 = realloc(a2, a2_n*sizeof(int)); if(a1 == NULL || a2 == NULL) { exit(1); } memcpy(a1, a, a1_n*sizeof(int)); // copio la prima metà dell'array memcpy(a2, &a[a1_n], a2_n*sizeof(int)); // copio la seconda metà dell'array mergeSort(a1, a1_n); // reitero la funzione sulla prima metà mergeSort(a2, a2_n); // reitero la funzione sulla seconda metà // ordino i risultati x=0; // dimensione del primo array y=0; // dimensione del secondo array for(i=0; i<(a1_n+a2_n); i++) { if((x<a1_n && a1[x]<=a2[y]) || y>=a2_n) { // se (a1 non è vuoto e a1<=a2) oppure se a2 è vuoto a[i] = a1[x]; x++; } else { a[i] = a2[y]; y++; } } free(a1); free(a2); }
Per maggiori informazioni circa la sintassi del linguaggio si faccia riferimento alla guida al Linguaggio C.