/*Programa que emplea un doble puntero para leer una serie de
  nombres (cadenas de caracteres), luego las ordena y finalmente
  imprime la lista ordenada. La cantidad de elementos en cada
  dimensión se asignará en forma exacta.
*/

#include<stdio.h>
#include<string.h>

// Encabezados de funciones:

   void leeDatos(char **&, int &); // El puntero debe pasar por referencia
   // porque es dentro de la función donde se le asignará la dirección de
   // la estructura formada

   void ordenar (char **, int, int);
   void imprimir(char **, int);
   char * leeCadena(void);
   void cambiar(char**, int, int);

void main (void)
{ int numDatos;      // Indicar  el número de  datos leídos
  char **nombre;     // puntero doble, aun no apunta a una dirección válida

  leeDatos(nombre, numDatos);
  ordenar(nombre, 0, numDatos-1);  // Se empelar  el método QuickSort
  imprimir(nombre,numDatos);

}

void leeDatos(char **&nombre, int &numDatos)
{  char *buffer[500]; //arreglo estático temporal, se destruirá cuando se
                      // termine la función
   numDatos=0;
   while (1)
    {  buffer[numDatos]=leeCadena();
       if (buffer[numDatos]==NULL) break;
       numDatos++;
    }
   // Ahora se le asigna a "nombre" la cantidad exacta de elementos leídos
   nombre = new char*[numDatos];
   // Finalmente le asignamos a cada elemento de "nombre" las direcciones
   // a las que apuntan los elementos de buffer;
   for(int i=0; i<numDatos; i++)
     nombre[i] = buffer[i];
}

// Todo lo dem s es igual, incluso se puede mantener los parámetros como
// char *nombre[] en lugar de char **nombre

void ordenar (char **nombre, int izq, int der)
{  // Ordena por el m‚todo QuickSort

   int limite; // Marca el límite entre los mayores y menores que el pivot
   if (izq>=der) return;
   cambiar(nombre, izq, (izq+der)/2); //Pone el pivot en la primera posición

   limite=izq;
   for (int i=izq+1; i<=der; i++)
      if (strcmp(nombre[i],nombre[izq])<0)
         cambiar(nombre,++limite,i);

   cambiar(nombre,izq,limite);
   ordenar(nombre,izq,limite-1);
   ordenar(nombre,limite+1,der);
}

void imprimir(char **nombre, int numDatos)
{ int i;
  for (i=0; i<numDatos; i++)
    printf("%3d) %s\n",i+1, nombre[i]);
}

char * leeCadena(void)
{  char buffer[300], *auxSt;
   int longSt;

   gets(buffer);
   longSt = strlen(buffer);
   if (longSt) // Si su longitud es diferente de cero
    {  // se reserva un espacio exacto de memoria y se copia
       auxSt = new char[longSt+1];
       strcpy(auxSt, buffer);
       return auxSt;
    }
   return NULL;
}

void cambiar(char**nombre, int i, int j)
{ char *aux;
  // se intercambian s¢lo los punteros
  aux = nombre[i];
  nombre[i]=nombre[j];
  nombre[j]=aux;
}