[C con Clase] De José Enrique

[Manuel L.]

Hola, José Enrique Hernández Ramírez:

P> ¿Cuál sería la idea a seguir para la implementación de algún método existente de ordenamiento aplicado a las listas y a los árboles? Si es posible.

La idea es siempre la misma: que se cumpla una relación de orden entre los elementos. La diferencia es que en la lista los elementos se disponen secuencialmente y por tanto la relación será binaria, mientras que en los árboles los elementos se disponen arborescentemente y, de ser binarios, la relación será ternaria. Respecto a las listas cualquier método de ordenación que haya visto es aplicable. Si la implementación de las listas permite acceso aleatorio en tiempo constante (la lista es estática o dinámica con sublistas estáticas, por ejemplo) entonces los métodos clásicos son directamente aplicables; si no deberá o plantearse usar otra implementación o bien transferir momentáneamente los elementos de la lista a un vector y realizar allí la ordenación. En caso de los árboles, piense en ordenaciones como los montículos, los árboles equilibrados (o balanceados)... recuerde que en la librería estándar de C++ la clase vector implementa objetos lista con acceso aleatorio y puede usarlo en el procedimiento sort contenido en la cabecera algorithm. Si únicamente desea conservar orden en listas quizás esta sea una implementación adecuada para su problema.

P> Cuando lo que se tienen son números la idea( o criterio ) del ordenamiento es sencilla(ya sea de mayor a menor o al revés. Corríjanme si estoy equivocado)¿Qué criterio se tiene en cuenta para ordenar objetos?

La idea es siempre la misma: que se cumpla una relación de orden entre los elementos. ¿Qué relación? ¡No importa! Puede ser efectivamente de mayor a menor, puede ser que los primos vayan primero y en lo demás de mayor a menor salvo el número 3 que es el mayor de todos... con los objetos sucede lo mismo, pero, naturalmente, el criterio que sirva para ordenar tendrá que adecuarse a la naturaleza del objeto. En cualquier caso: puede abstraer los criterios para la ordenación en objetos o en funciones (como prefiera) y definir un método de ordenación genérico que simplemente ordene los elementos atendiendo a la relación que el programador le brinde. En C típicamente se hace con punteros a funciones y el manejo de punteros a void; en C++, mediante objetos (como en la librería estándar de C++) o mediante punteros a funciones y plantillas de funciones. Como esta es una lista de C++ supondré que es C++ lo que pretende usar, y como una de las implementaciones mediante objetos ya la puede encontrar en la librería estándar le ejemplifico el uso de las plantillas de funciones:


***********************
*  Fichero ejemplo.h  *
***********************

/* EJEMPLO de como implementar una ordenacion con independencia de los objetos
a usar. Para ello se realizan tres ordenaciones: un vector de enteros de mayor
a menor, un vector de enteros de mayor a menor salvo que todo par es mayor que
cualquier impar, y un vector de objetos de la clase string de menor a mayor */

#include <string>
	using std::string;


/* Plantilla de funcion para quicksort, para que el compilador sustituya donde
sea necesario T por el tipo de datos que sea necesario */
template <typename T>
void quicksort(T *v,int tamano,bool (*relacion)(const T &o1,const T &o2));

// Plantilla de funcion para imprimir cualquier tipo de vector
template <typename T>
void imprimirVector(const T *v,int tamano);


// Funcion que implementa la relacion de orden de menorQue en enteros
bool enteroMayorQueEntero(const int &e1,const int &e2);

// Funcion que implementa la segunda relacion de orden entre enteros descrita
bool enteroMayorQueEspecialEntero(const int &e1,const int &e2);

// Funcion que implementa la relacion de orden menorQue en objetos string
bool StringMenorQueString(const string &s1,const string &s2);


// Punto de entrada al programa
int main();


*************************
*  Fichero ejemplo.cpp  *
*************************

#include <algorithm>
	using std::swap; // intercambia el contenido de dos variables
#include <iostream>
	using std::cout;
#include "ejemplo.h"


template <typename T>
void quicksort(T *v,int tamano,bool (*relacion)(const T &o1,const T &o2))
	{

	int tamanoPrimeraParte = 0;
	T pivote = *(v + tamano/2);
	swap(*(v + tamano/2),*(v + tamano - 1)); // asi el pivote quedara de ultimo
	T *pSegundaParte = v,*pTmp = v;
	for(int i=tamano;i;--i)
		{
		if( (*relacion)(*pTmp,pivote) )
			{
			swap(*pSegundaParte,*pTmp);
			++tamanoPrimeraParte;
			++pSegundaParte;
			}
		++pTmp;
		}

	swap(*(v + tamano - 1),*pSegundaParte); // se coloca el pivote entre ambas partes
	if(tamanoPrimeraParte > 1) quicksort(v,tamanoPrimeraParte,relacion);
	if(tamano - tamanoPrimeraParte  > 1) quicksort(++pSegundaParte,tamano-tamanoPrimeraParte-1,relacion);

	}


template <typename T>
void imprimirVector(const T *v,int tamano)
	{

	--tamano;
	for(int i=0;i<tamano;++i) cout << v[i] << ", ";
	cout << v[tamano] << ";\n";

	} 


bool enteroMayorQueEntero(const int &e1,const int &e2) { return e1 > e2; }


bool enteroMayorQueEspecialEntero(const int &e1,const int &e2)
	{

	if(e1 % 2)
		if(e2 % 2) return e1 > e2;
		else return false;
	else
		if(e2 % 2) return true;
		else return e1 > e2;

	}


bool StringMenorQueString(const string &s1,const string &s2) { return s1 < s2; }


// Punto de entrada al programa
int main()
	{

	int v1[5] = { 4,1,8,3,2 };
	cout << "\n\nv1 antes de la ordenacion:\n";
	imprimirVector(v1,5);
	quicksort(v1,5,enteroMayorQueEntero);
	cout << "v1 despues de la ordenacion:\n";
	imprimirVector(v1,5);

	int v2[5] = { 4,1,8,3,2 };
	cout << "\nv2 antes de la ordenacion:\n";
	imprimirVector(v2,5);
	quicksort(v2,5,enteroMayorQueEspecialEntero);
	cout << "v2 despues de la ordenacion:\n";
	imprimirVector(v2,5);

	string v3[5] = { "util","esta","Ojala","considere","muestra" };
	cout << "\nv3 antes de la ordenacion:\n";
	imprimirVector(v3,5);
	quicksort(v3,5,StringMenorQueString);
	cout << "v3 despues de la ordenacion:\n";
	imprimirVector(v3,5);

	cout << "\n\n";
	return 0;

	}