//Gonzalez ortega carlos	  
//materia: Estructura de Datos	Grupo  : 2802
//Profesor: Rubio Alejandro	
// Programa que realiza ordenacion por el Metodo de Quick Short       

#include "stdio.h"
#include "conio.c"
#define N 100	/*maximo de elementos*/
#define M 50	/*mitad de elementos que N*/

main(){
  int mayor[M]={0},	/*arreglo auxiliar*/
      menor[M]={0}, /*arreglo auxiliar*/
      a[N]={0};	/*arreglo principal*/
  int aux,	/*variable auxiliar para intercambio de elementos*/
      n,	/*tama¤o del arreglo*/
      ban;
  int der,	/*posicion a la derecha*/
      izq,	/*posicion a la izquierda*/
      top;	/*tope del arreglo*/
  int ini,      /*posicion inicio*/
      fin,	/*posicion final*/
      pos,	/*posicion*/
      i;

	clrscr();
    gotoxy(20,2); printf("Ordenacion por el Metodo de Quick Sort");
	gotoxy(5,6);printf("Introduzca el tamaņo del arreglo: ");
	gotoxy(5,40);scanf("%d", &n);/*lee el tama¤o del arreglo*/
    gotoxy(5,8);printf("Valores del arreglo: ");
	for (i=1; i<=n; i++)
		{gotoxy(i*4+1,9);scanf("%d", &a[i]);}/*lee y almacena los elementos en el arreglo principal*/
                 	top=1;	/*inicio del tope del arreglo*/
	menor[top]=1;	/*almacena el valor 1 en la posicion top del arreglo menor*/
	mayor[top]=n;	/*almacena el valor de n(tama¤o del arreglo) en la posicion top del arreglo mayor*/

	while (top > 0) {/*Mientras la posicion top sea mayor que 0*/
		ini=menor[top];/*ini toma el elemento contenido en la posicion top del arreglo menor*/
		fin=mayor[top];/*fin toma el elemento contenido en la posicion top del arreglo mayor*/
		top--;/*decrementa la posicion top menos uno*/
		izq=ini;/*izq toma el valor de ini*/
		der=fin;/*der toma el valor de fin*/
		pos=ini;/*pos toma el valor de ini*/
		ban=1;/*variable de desicion a ordenar toma el valor 1*/

		while (ban){/*mientras ban valga 1*/
			while ((a[pos]<=a[der]) && (pos!=der))/*disminuye el valor de der si el valor del elemento en a[pos] es menor*/
				der--;			      /*que a[der] y ademas pos es diferente que der*/
			if (pos==der)/*si las posiciones son iguales*/
				ban=0;	/*cambia el valor de ban*/
			else{/*hace el cambio de elementos*/
				aux=a[pos];/*aux toma el valor mayor contenido en la posicion pos del arreglo*/
				a[pos]=a[der];/*el arreglo en la posicion pos almacena el valor menor contenido en la posicion derecha*/
				a[der]=aux;/*el arreglo en la posicion der toma el elemento mayor contenido en aux*/
				pos=der;/*la variable de posicion pos toma el valor de la nueva posicion contenida en der*/
				while ((a[pos] >= a[izq]) && (pos != izq))/*mientras el elemento contenido en la posicion pos del arreglo sea mayor o igual*/
					izq++;		/*que el elemento contenido en la posicion izq del arreglo y el valor de pos sea diferente del valor de izq incrementa el valor de izq mas uno*/
				if (pos==izq)/*si las posiciones son iguales cambia el valor de ban*/
					ban=0;
				else{/*si el valor contenido en la posicion pos es menor que el contenido en la posicion izq del arreglo hace el cambio*/
					aux=a[pos];/*aux toma el elemento menor contenido en la posicion pos del arreglo*/
					a[pos]=a[izq];/*se almacena el elemento mayor contenido en la posicion izq en la posicion pos del arreglo*/
					a[izq]=aux;/*se almacena el elemento menor contenido en aux en la posicion izq del arreglo*/
					pos=izq;/*pos toma la nueva posicion del arreglo almacenada en izq*/
				}
			}
		}
		if (ini<(pos-1)){/*si el valor de la posicion ini es menor que el valor de la posicion pos-1*/
			top++;/*se incrementa el valor de la posicion top mas uno*/
			menor[top]=ini;/*almacena el valor de la posicion ini en la posicion top del arreglo menor*/
			mayor[top]=pos-1;/*almacena el valor de la posicion pos-1 en la posicion top del arreglo mayor*/
		}
		if (fin>(pos+1)){/*si el valor de la posicion fin es mayor que el valor de la posicion pos+1*/
			top++;/*incrementa el valor de la posicion top mas uno*/
			menor[top]=pos+1;
			mayor[top]=fin;
		}
	}
	gotoxy(5,12); printf("Arreglo ordenado: ");
	for (i=1; i<=n; i++)
		printf("%d  ", a[i]);/*imprime el arreglo ordenado*/
	getch();
  return 0;
}