#include <iostream>
#include <cstdlib>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
#define Max 100
 
using namespace std;
FILE *doc;
 
void OrdenaBur(int , char [Max][Max], char [Max]);//mis funciones
void QS(char [Max][Max],int,int);
void MShell(int , char [Max][Max]);
void Imprimir(int , char [Max][Max]);
void Guardar(int , char [Max][Max]);
 
 
 
int main() {
	int Tam;
 
	char arreglo[Max][Max], temp[Max], preg;
	int Menu;
 
 
	cout 	 << "  Metodos de ordenamiento"<<endl;
	cout << "Seleccione una opcion"<<endl;
	cout <<"1.Ingresar Datos"<<endl;
    cout <<"2.Mostrar Datos"<<endl;
    cout <<"3.Metodo QuickSort"<<endl;
	cout <<"4.Metodo Burbuja"<<endl;
    cout <<"5.Metodo Shell"<<endl;
    cout <<"6.Salir"<<endl;
 
	 cin >> Menu;
 
	do{//mi menu
		system("cls");
 
		cout << "\n\n\t 1.Ingresar Datos\n 2.Mostrar Datos\n 3.Metodo QuickSort"
		 << "\n 4.Metodo Burbuja\n 5.Metodo Shell\n "
		 << "\n 7.Salir\n";
		 if(Menu=='\0')
		 {
		 	cout  << "\t\tSeleccione la opcion\n";
		 	cin >> Menu;
	}
	switch(Menu){
 
		case 1:
		{
			cout << "Ingrese la cantidad de cadenas que desee ordenar\n";
			cin >> Tam;
			Tam--;
			Guardar(Tam, arreglo);
			break;
		}
		case 2:
		{
 
			cout << "\nSus cadenas ingresadas son las siguientes\n"<<endl;
			Imprimir(Tam, arreglo);
			break;
		}
		case 3:
		{
			QS(arreglo,0,Tam);
			Imprimir(Tam,arreglo);
			break;
		}
		case 4:
		{
			OrdenaBur(Tam,arreglo,temp);
			Imprimir(Tam,arreglo);
			break;
		}
		case 5:
		{
			MShell(Tam, arreglo);
			Imprimir(Tam,arreglo);
			break;
		}
		case 6:
		{
				return 0;
			    break;
		}
 
		default:
		cout << "Error, Debe ingresar un dato valido\n";
	}
	cout << "\nDesea volver al menu?"
		 << "\n s para volver\n n para salir\n";
	cin >>preg;
	Menu='\0';
}
while(preg=='s');
	return 0;
}
void OrdenaBur(int Tam, char arreglo[Max][Max], char temp[Max])
{
	int tb, rg;
	cout << "\n\nSus cadenas ordenadas alfabeticamente con el metodo burbuja son: \n" << endl;
 
	for(tb=0; tb<Tam; tb++)
		for(rg=tb+1; rg<Tam+1; rg++)
			if(strcmpi(arreglo[tb], arreglo[rg])>0)
			{
			strcpy(temp, arreglo[tb]);
			strcpy(arreglo[tb], arreglo[rg]);
			strcpy(arreglo[rg], temp);
			}
}
void QS(char arreglo[Max][Max],int limite_izq,int limite_der)
{
 
    int izq,der,prob;
    char temporal[Max],pivote[Max];
    cout << "\n\nSus cadenas ordenadas \n"
		<< "alfabeticamente con el metodo quick sort son: \n" << endl;
 
    izq=limite_izq;
    der = limite_der;
    strcpy(pivote,arreglo[(izq+der)/2]);
 
    do
	{
 
        while(strcmpi(arreglo[izq],pivote)<0)
		izq++;
        while(strcmpi(arreglo[der],pivote)>0)
		der--;
        if(strcmpi(arreglo[izq],arreglo[der])>=0)
        {
            strcpy(temporal,arreglo[izq]);
            strcpy(arreglo[izq],arreglo[der]);
			strcpy(arreglo[der],temporal);
            izq++;
            der--;
        }
 
    }
	while(izq<=der);
 
    if(limite_izq<der)
	QS(arreglo,limite_izq,der);
    if(limite_der>izq)
	QS(arreglo,izq,limite_der);
}
void MShell(int Tam, char arreglo[Max][Max])
{
	int i,j,k;
	char aux[Max] ;
	cout << "\n\nSus cadenas ordenadas alfabeticamente con el metodo shell sort son: \n" << endl;
	k=Tam/2;
 
	while(k>0)
	{
		for(i=k/*+1*/;i<=Tam;i++)
		{
			j=i-k;
			while(j>=0)
			{
				if(strcmp(arreglo[j],arreglo[j+k])>=0)
				{
					strcpy(aux,arreglo[j]);
					strcpy(arreglo[j],arreglo[j+k]);
					strcpy(arreglo[j+k],aux);
				}
				else
				{
					j=0;
				}
			j=j-k;
			}
		}
	k=k/2;
	}
}
 
 
 
void Guardar(int Tam, char arreglo[Max][Max])
{
	int cont;
	for (cont=0;cont<=Tam;cont++)
	{
		cout << "\nCadena "<<cont+1<<endl;
		cin >> arreglo[cont];
	}
}
void Imprimir(int Tam, char arreglo[Max][Max])//Mi duda con los archivos
{
    int c;
    doc= fopen("alfabetico.txt","r");
    if (doc==NULL){
    cout<<"Error con el archivo"<<endl;
 
     while((c=getc(doc))!=EOF){
     if(c=='\n'){
      cout<<endl;
     }
      else {
     cout<<c;
     }
 
     fclose(doc);
 
     }
 
    }
}