Vamos a ver, en esta ocasión, un nuevo ejemplo de lo que es programación recursiva en C. Mi propósito es mostraros en qué consistiría la ordenación de un vector de números enteros mediante el método mergesort. Probablemente sea uno de los sistemas más complejos y difíciles de entender. Empero, es un conocimiento básico para cualquier programador novel.

Este algoritmo también es un típico ejemplo de divide y vencerás. Es decir, subdividiremos el problema en otros más pequeños similares al original con el objetivo de que sean fácilmente resolubles. Entonces procederemos a unir los subproblemas hasta que lleguemos al problema original.

Conceptualmente se trataría de realizar los siguientes pasos:

  • Si la lista tiene una longitud entre 0 y uno, entonces ya está ordenada. En otro caso
  • Dividir la lista desordenada en dos sublistas de aproximadamente el mismo tamaño.
  • Ordenar cada sublista recursivamente utilizando el ordenamiento por mezcla
  • Mezclar las dos sublistas en una lista ordenada.

Os mostraré el fichero de cabecera:

#ifndef MERGESORT_H_
#define MERGESORT_H_

void merge ( int* a, int b, int m, int e );
void mergesort ( int* a, int b, int e );

#endif /* MERGESORT_H_ */

A continuación os dejo el código fuente principal de los dos procedimientos anteriores:

void merge ( int* a, int b, int m, int e ) {

	int l = m - b + 1;
	int r = e - m;
	int i;

	int L[l+1], R[r+1];

	for ( i=0; i<l; i++ ) {
		L[i] = a[b+i];
	}

	for ( i=0; i<r; i++ ) {
		R[i] = a[m+i+1];
	}

	L[l] = 32767;
	R[r] = 32767;
	l = 0;
	r = 0;

	for ( i=0; i<e-b+1; i++ ) {
		if (L[l] < R[r]) {
			a[b+i] = L[l];
			l++;
		}
		else {
			a[b+i] = R[r];
			r++;
		}
	}

}

void mergesort ( int* a, int b, int e ) {

	if ( b < e ) {
		int m = (b + e) / 2;
		mergesort ( a, b, m );
		mergesort ( a, m+1, e );

		merge ( a, b, m, e );
	}

}

Por último, aquí tenéis un programa de prueba con el que podréis comprobar como funciona.

void merge ( int* a, int b, int m, int e ) {

	int l = m - b + 1;
	int r = e - m;
	int i;

	int L[l+1], R[r+1];

	for ( i=0; i<l; i++ ) {
		L[i] = a[b+i];
	}

	for ( i=0; i<r; i++ ) {
		R[i] = a[m+i+1];
	}

	L[l] = 32767;
	R[r] = 32767;
	l = 0;
	r = 0;

	for ( i=0; i<e-b+1; i++ ) {
		if (L[l] < R[r]) {
			a[b+i] = L[l];
			l++;
		}
		else {
			a[b+i] = R[r];
			r++;
		}
	}

}

void mergesort ( int* a, int b, int e ) {

	if ( b < e ) {
		int m = (b + e) / 2;
		mergesort ( a, b, m );
		mergesort ( a, m+1, e );

		merge ( a, b, m, e );
	}

}

Este artículo se basa en la publicación que podéis visitar en el siguiente enlace. Como siempre, quedo a vuestra disposición para resolver cualquier duda que os surja.

Dejar respuesta

Please enter your comment!
Please enter your name here