/*Programa que emplea un arreglo de punteros para leer una serie
  de nombres (cadenas de caracteres), luego los ordena y finalmente
  imprime la lista ordenada
*/

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

// Encabezados de funciones:

   void leeDatos(char *[], int &);
   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[100]; // Cada elemento del arreglo apunta 
                     // a un arreglo de caracteres

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

}

void leeDatos(char *nombre[], int &numDatos)
{  numDatos=0;
   while (1)
    {  nombre[numDatos]=leeCadena();
       if (nombre[numDatos]==NULL) break;
       numDatos++;
    }
}

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;
}