Autor Tema: Re: Necesito conocer el funcionamiento interno del QuickSort (Leído 4871 veces)

Marta · « **en:** Miércoles 26 de Marzo de 2003, 00:47 »

¿se podría implementar la funcion del QuickSort sin utilizar un puntero a una funcion?
Podría ordenar strings, enteros, etc. sólo variando la funcion externa de comparación, no?
¿Podrías explicarmelo?

JuanK

Claro que se puede...pero conoces el fuincionamiento básico del algoritmo?
es decir la ordenacion de enteros?

No es nada complicado lo que pides pero si un poco largo de hacer, lo del puntero es lo de menos, todo depende de como hagas tu aplicacion.
Obviamente la funcion de ordenamiento de enteros no te sirve para cadenas , por ello te pregunto si conoces bien el algoritmo , ya que hay que modificarlo segun tus necesidades.

Marta

Pero yo me refiero al funcionamiento interno, al codigo que no vemos. De todas formas, sabrías implementarlo para que ordene tanto strings como enteros?
Yo tengo implementado el q me ordena strings, pero con el de enteros me estoy peleando aun. Podías ayudarme.
Gracias por contestar de todas formas.

gmantil

Hola Marta:
El funcionamiento del QuickSort es el siguiente:

Se calcula un indice a la mitad del vector a ordenar.

Se comparan los elementos de la izquierda contra ese elemento medio hasta encontrar un elemento mayor al de la mitad.

Se comparan los elementos de la derecha contra el mismo elemento medio citado arriba hasta encontrar un elemento menor al de la mitad.

Cuando tenemos un mayor a la izquierda y un menor a la derecha, los intercambiamos entre sí.

Volvemos a mirar los de la izquierda restantes contra el de la mitad bajo el mismo criterio anterior, igual hacemos con los de la derecha y volvemos a intercambiar.

Esto se repite en un ciclo hasta que el indice por izquierda supere o sea igual al indice por derecha.

Saliendo de este ciclo el llamado se hace de nuevo recursivo, primero por izquierda considerando un subvector entre el inicio del vector y el indice por derecha.

Luego se hace un llamado recursivo por derecha considerando un subvector desde el indice por izquierda y el limite del vector por derecha.

Este es el funcionamiento de este algoritmo de naturaleza recursivo. Si quieres convertirlo por ciclos, debes entender primero bien su naturaleza pura.

gmantil

JuanK

No te entiendo aún... no conoces el algoritmo?.. te referias alo que respondio gmantill?

Por cierto, lo de hacerlo con punteros facilita muchisimo las cosas, seguramente que debe haber muchas otras formas de hacerlo , pero esta es la más efectiva y natural, de todos modos los limites los puedes vencer, sino te gusta hacerlo con punteros,,, tendras que quemarte la cabeza como 1000 veces para implementar el algoritmo con otro sistema
en todo caso... aqui te anexo una página donde encontraras una referencia del algoritmo basico, nuevamente su explicacion,ejemplo y codigo fuente, todo esto para trabajo con arays de enteros de longitud fija, no exactamente con punteros, ya que se mueven de una manera mucho más natural por ser en un array estatico:
http://galeon.com/analisisdealgoritmos/ ... 28098.html

Sin embargo, si te interesa, estoy trabajando por ahi en un software educativo, y para lo cual necesite algo de trabajo con el QuickSort y con solo apuntadores, asi que no le veo inconveniente, al publicar el segmento correspondiente al mismo.
El algoritmo realiza el ordenamiento quicksort a una estructura dinámica que almacena numeros enteros, segun como se ve en el siguiente código; adicionalemente utilizo algunas funciones adicionales que hice para facilitar el trabajo:

Código: Text

 
/*[b]Definicion de la estructura o tipo de dato[/b]*/
 
struct Data
{
   struct Data *Pre;
   int info;
   struct Data *Post;
};
/*una vez definida es necesario llenarla con datos lo cual se hace en otra funcion
[b]Algoritmo quicksort[/b]
Este  recive una estructura con datos y los ordena*/
void INquicksort(struct Data *rider,int desde,int hasta)
{
  int izq,der,cont,CRUCE=0;
  struct Data *IZQ,*DER,*DESDE,*HASTA;
 
  if(desde<hasta)//si el array o subarray es mayor a 1 item
  { // Valores iniciles de la b£squeda.
    cont=Counter(rider);
    izq=desde+1;
    der=hasta;
    IZQ=(struct Data *)MoveToN(rider,izq);
    DESDE=(struct Data *)MoveToN(rider,desde);
    DER=HASTA=(struct Data *)MoveToN(rider,hasta);
    while(!CRUCE)
    {
      while(IZQ!=HASTA && IZQ->info<=DESDE->info)//busqueda de un # mayor
      {
        IZQ=IZQ->Post;
      }
      while(DER!=DESDE && DER->info>=DESDE->info)//busqueda de un # menor
      {
        DER=DER->Pre;
      }
      if(MyNumber(IZQ)<MyNumber(DER)) // si no se han cruzado:
      {
        IZQ->info+=DER->info; // Intercambiar.
        DER->info=IZQ->info-DER->info;
        IZQ->info-=DER->info;
      }
      else // si se han cruzado:
       CRUCE=1;// salir del bucle.
    }
    //el m s peque¤o, desde se cambia con ‚l menor encontrado.
    if(DER!=DESDE)
    {
      DER->info+=DESDE->info;// Colocar el pivote
      DESDE->info=DER->info-DESDE->info; // en su posici¢n.
      DER->info-=DESDE->info;
    }
    if(MyNumber(DER)!=1)
      INquicksort(rider,desde,MyNumber(DER->Pre)); // Ordenar el primer array.
    if(MyNumber(DER)!=cont)
      INquicksort(rider,MyNumber(DER->Post),hasta); // Ordenar el segundo array.
  }
}
 
/*[b]Funciones Complementarias para manejar la estructura[/b]
 
Deja el apuntador de una estructura en el primer registro*/
struct Data *GoFirst(struct Data *dat)
{
  while(dat->Pre!=NULL)
    dat=dat->Pre;
  return dat;
}
 
/*Funcion para pruebas de datos
  lo que hace es imprimir
  una estructura de tipo Data->info
  En pantalla*/
void PrintGDF(struct Data *MyPrint)
{
 MyPrint=(struct Data *)GoFirst(MyPrint);
 while (MyPrint->Post!=NULL)
 {
   printf("%dn",MyPrint->info);
   MyPrint=MyPrint->Post;
 }
}
 
/*Devuelve el numero de nodos de la estructura*/
int Counter(struct Data *items)
{
  int cont=0;
  items=(struct Data *)GoFirst(items);
 
  while(items->Post!=NULL)
  {
    cont++;
    items=items->Post;
  }
  return cont;
}
 
//devuelve el numero del nodo actual.
int MyNumber(struct Data *items)
{
  int cont=1;
  struct Data *aux;
  aux=(struct Data *)GoFirst(items);
  while(aux!=items)
  {
    cont++;
    aux=aux->Post;
  }
  return cont;
}
 
//cambia el apuntador a la posicion indicada.
struct Data *MoveToN(struct Data *items,int GoToNumber)
{
  items=(struct Data *)GoFirst(items);
  int i;
  for(i=1;i<GoToNumber;i++)
    items=items->Post;
  return items;
}
 
 

Espero que te sirva, mucha suerte con tu trabajo, por ahora me voy a descansar porque hoy he tenido mucho trabajo.. y mañana... es decri en unas horas... meespera aun mas trabajo..

Juank.

:angel:nota: te recomeindo que para entenderlo , le realices una prueba de escritorio, con una estructura que apunte a un lista de 10 nodos sera suficiente para que puedas entender que es lo que hace.