SoloCodigo
Programación General => C/C++ => Mensaje iniciado por: nicokiki en Lunes 13 de Octubre de 2003, 16:45
-
Alguien tiene el codigo del Quicksort hecjho para templates y para vector de la Standard Template Library???
:question:
-
de que lenguaje estas hablando.. no te entendi.
-
Tengo que implementar el metodo de ordenamiento Quicksort utilizando templates, esto es, que soporte cualquier tipo de datos a ordenar, pero que los datos esten en un vector de la Standard Template Library
Algo asi seria el encabezado:
template <class Tipo> void QuickSort(std::vector<Tipo>& vec, std::vector<Tipo>::iterator low,
std::vector<Tipo>::iterator high)
Ya que estoy meto todo el codigo. Hay algo que me parece que no esta bien y no se que es (yo lo uso para un tipo de datos mio que tiene sobrecargado los operadores "<", ">" y el "==" y se que estan bien sobrecargados entonces no se cual es el prblema de mi programa)
Ahi va el codigo
#include <vector>
template <class Tipo> std::vector<Tipo>::iterator Partition(std::vector<Tipo>& vec, std::vector<Tipo>::iterator left /*low*/,
std::vector<Tipo>::iterator right/*high*/)
{
// std::vector<Tipo>::iterator left, right;
Tipo pivot_item, aux;
// std::vector<Tipo>::iterator pivot = left = low;
//pivot_item = *low;
pivot_item = *left;
// right = high;
while ( left < right )
{
while ( **left < *pivot_item )
left++;
while ( **right > *pivot_item)
right--;
if ( left < right )
{
if (**left > **right)
{
aux = *left;
*left = *right;
*right = aux;
}
else
{
++left;
--right;
}
}
}
//*left = *right;
//*right = pivot_item;
return right;
}
template <class Tipo> void QuickSort(std::vector<Tipo>& vec, std::vector<Tipo>::iterator low,
std::vector<Tipo>::iterator high)
{
std::vector<Tipo>::iterator pivot;
if ( high > low )
{
pivot = Partition(vec, low, high);
QuickSort(vec, low, pivot - 1);
QuickSort(vec, pivot + 1, high);
}
}
Hay comentarios que no he eliminado, les pido disculpas porque no es lindo para leer.
Espero que con esta aclaracion alguien me pueda ayudar.
-
Pero el problema es que nunca he manejado STL...
Igual la implementacion se supone que la debes saber hacer tu , porque a fin de cuentas tu has definido tu tipo de datos y debes definir un criterio de ordenamiento.
De este modo el ordenamiento se hace igual que con el quicksort aplicado a un array o a una estructura enlazada.
Si lo necesitas te puedo pasar la explicacion en pseudocodigo para realizar el quicksort en arrays.. solo deberas utilizar y modificar el algoritmo para tu template.
No es muy dificil, de hecho es más dificil modificarlo para utilizarlo con una lista doblemente enlazada.. y yo ya lo hice.
Si te sirve de algo me avisas y te posteo el codigo para listas doblemente enlazadas.