• Domingo 15 de Diciembre de 2024, 03:01

Autor Tema:  Re: Quicksort  (Leído 1172 veces)

nicokiki

  • Miembro MUY activo
  • ***
  • Mensajes: 298
    • Ver Perfil
Re: Quicksort
« en: Lunes 13 de Octubre de 2003, 16:45 »
0
Alguien tiene el codigo del Quicksort hecjho para templates y para vector de la Standard Template Library???
:question:

JuanK

  • Miembro de ORO
  • ******
  • Mensajes: 5393
  • Nacionalidad: co
    • Ver Perfil
    • http://juank.io
Re: Quicksort
« Respuesta #1 en: Miércoles 15 de Octubre de 2003, 17:36 »
0
de que lenguaje estas hablando.. no te entendi.
[size=109]Juan Carlos Ruiz Pacheco
[/size]
Microsoft Technical Evangelist
@JuanKRuiz
http://juank.io

nicokiki

  • Miembro MUY activo
  • ***
  • Mensajes: 298
    • Ver Perfil
Re: Quicksort
« Respuesta #2 en: Jueves 16 de Octubre de 2003, 01:11 »
0
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.

JuanK

  • Miembro de ORO
  • ******
  • Mensajes: 5393
  • Nacionalidad: co
    • Ver Perfil
    • http://juank.io
Quicksort
« Respuesta #3 en: Jueves 16 de Octubre de 2003, 14:53 »
0
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.
[size=109]Juan Carlos Ruiz Pacheco
[/size]
Microsoft Technical Evangelist
@JuanKRuiz
http://juank.io