// Thomas

// An example sorting procedure, based on the insertion-sort
// algorithm. Note that it is inefficient for large arrays.
// Also note that the code slightly differs from the lecture
// notes, because the array in C begins with index 0.

//THE ONE THAT WORKS THE FASTEST OUT OF THE ONES I'VE DONE





#include<stdlib.h>
#include<stdio.h>

typedef struct {
	int p;
	int r;
} stack;


void sort(int *a, int n)
{
	
	
	int x, i, j, temp;		// p, r; 
	stack *yes;
	int ptr = 0; 
	yes = (stack *)malloc(sizeof(stack)* (n/2));
	yes[ptr].p = 0;
	yes[ptr++].r = n - 1;
	//ptr = ptr + 1;
	while (ptr > 0)
	{	
		ptr = ptr - 1;		
		//p = yes[ptr].p;
		//r = yes[ptr].r;
	
		//if (p < r)
		if ((yes[ptr].p) < (yes[ptr].r))
		{	
					//x = a[p];
			
			x = a[yes[ptr].p];
			i = yes[ptr].p - 1;
			j = yes[ptr].r + 1;
					//i = p - 1;
					//j = r + 1;
			while(1)
			{
				do {
					j = j - 1;
				} while (a[j] > x);
				do {
					i = i + 1;
				} while (a[i] < x);
				if (i < j)
				{	temp = a[j];
					a[j] = a[i];
					a[i] = temp;
				} else break;
			}
			//if ((yes[ptr].r - j + 1) > (j - yes[ptr].p) )
			//{		
				//yes[ptr].r = r;
				temp = yes[ptr].p;
				yes[ptr].p = j + 1;
				ptr = ptr + 1;
				yes[ptr].r = j;
				yes[ptr].p = temp;
				ptr = ptr + 1;
			/*} else {
				temp = yes[ptr].r;
				yes[ptr++].r = j;
				//yes[ptr].p = p;
				//ptr = ptr + 1;
				yes[ptr].r = temp;
				yes[ptr++].p = j + 1;
				//ptr = ptr + 1;
				
			}*/
		}
	} 
}			


/*
#include<stdio.h>
#include<stdlib.h>
#include "p4stkadt.h"




void sort(int* a, int n)
{
	STACK *stack;
	int x, i, j, temp, p, r, m = 1;
	int *c, *b;
	stack = createStack();
	c = (int *)malloc(sizeof(int));
	*c = n - 1;
	pushStack(stack, (void *)c);
	b = (int *)malloc(sizeof(int));
	*b = 0;
	pushStack(stack, (void *)b);

	
	while (!emptyStack(stack))
	{	
		p = *((int *)popStack(stack));

		r = *((int *)popStack(stack));

		
		if (p < r)
		{
			
			x = a[p];
			i = p - 1;
			j = r + 1;

			while (m == 1)
			{	
				do {
					j = j - 1;
				} while (a[j] > x);
				do {
					i = i + 1;
				} while (a[i] < x);

				if (i < j) 
				{	temp = a[j];
					a[j] = a[i];
					a[i] = temp;
				} else break;

			}

		c = (int *)malloc(sizeof(int));
		*c = r;
		pushStack(stack, (void *)c);
		c = (int *)malloc(sizeof(int));
		*c = j + 1;
		pushStack(stack, (void *)c);
		c = (int *)malloc(sizeof(int));
		*c =  j;
		pushStack(stack, (void *)c);
		c = (int *)malloc(sizeof(int));
		*c = p;
		pushStack(stack, (void *)c);
		}

		
	}
}



*/


/*

void sort(int*a, int n)
{

	if (n < 30) {
		int i, j, key;
		for (j = 1; j < n; j++) {
			key = a[j];
			i = j - 1;
			while (i >= 0 && a[i] > key) 
			{
				a[i + 1] = a[i];
				i = i - 1;
			}
			a[i + 1] = key;
		}
	}
	else {
		void quickSort(int*, int, int);
		//int Partition(int*, int, int);
		quickSort(a, 0, n - 1);
	//}	

}

	void quickSort(int* a, int p, int r)
	{	
		int x, i, j, temp;
		//int q;
		if (p < r)
		{	//q = Partition(a, p, r);	
			
	
			//x = a[p];
			i = p - 1;
			j = r + 1;
			while (1)
			{
				do {
					j = j - 1;
				} while ( a[j] > a[p]);
				do { 
					i = i + 1;
				} while (a[i] < a[p]);
				if (i < j)			
				{	temp = a[j];
					a[j] = a[i];
					a[i] = temp;
				}
				else 
				{	break;
				}
			}
		
			quickSort(a, p, j);
			quickSort(a, j + 1, r);
		}
	}




	int Partition(int* a, int p, int r)
	{	int x, i, j, temp, m = 1;
	
		x = a[p];
		i = p - 1;
		j = r + 1;
		while (1)
		{
			do {
				j = j - 1;
			} while ( a[j] > x);
			do { 
				i = i + 1;
			} while (a[i] < x);
			if (i < j)	
			{	temp = a[j];
				a[j] = a[i];
				a[i] = temp;
			}
			else 
			{	return j;
			}
		}

	}


*/



/*
void sort(int* a, int n)
{
	void new_sort(int*, int, int);
	new_sort(a, 0, n);
}



    void brute(int a[], int lo, int hi) 
	{

	int pmax;
        if ((hi-lo) == 1) {
	    if (a[hi] < a[lo]) {
		int T = a[lo];
		a[lo] = a[hi];
		a[hi] = T;
	    }
	}
	if ((hi-lo) == 2) {
	    int pmin = a[lo] < a[lo+1] ? lo : lo+1;
	    pmin = a[pmin] < a[lo+2] ? pmin : lo+2;
	    if (pmin != lo) {
	        int T = a[lo];
		a[lo] = a[pmin];
		a[pmin] = T;
	    }
	    brute(a, lo+1, hi);
	}
	if ((hi-lo) == 3) {
	    int pmin = a[lo] < a[lo+1] ? lo : lo+1;
	    pmin = a[pmin] < a[lo+2] ? pmin : lo+2;
	    pmin = a[pmin] < a[lo+3] ? pmin : lo+3;
	    if (pmin != lo) {
                int T = a[lo];
	        a[lo] = a[pmin];
	        a[pmin] = T;
            }
	   
			pmax = a[hi] > a[hi-1] ? hi : hi-1;
            pmax = a[pmax] > a[hi-2] ? pmax : hi-2;
	    if (pmax != hi) {
                int T = a[hi];
                a[hi] = a[pmax];
	        a[pmax] = T;
	    }
	    brute(a, lo+1, hi-1);
        }
    }

    void new_sort(int* a, int lo0, int hi0) {
	void brute(int*, int, int); 
	int lo, hi, pivot;
	lo = lo0;
	hi = hi0;
	if ((hi-lo) <= 3) {
	    brute(a, lo, hi);
	    return;
	}


	 pivot = a[(lo + hi) / 2];
        a[(lo + hi) / 2] = a[hi];
        a[hi] = pivot;

        while( lo < hi ) {
            
            while (a[lo] <= pivot && lo < hi) {
		lo++;
	    }

            
	    while (pivot <= a[hi] && lo < hi ) {
		hi--;
	    }

            
            if( lo < hi ) {
                int T = a[lo];
                a[lo] = a[hi];
                a[hi] = T;
            }
	}

        
        a[hi0] = a[hi];
        a[hi] = pivot;

        
	new_sort(a, lo0, lo-1);
	new_sort(a, hi+1, hi0);
    }


*/

/*

#include <stdlib.h>

void sort(int* a, int n)
{
	int Randomized_Partition(int*, int, int);
	void Randomized_Quicksort(int*, int, int);
	Randomized_Quicksort(a, 0, n);
}

int Randomized_Partition(int* a, int p, int r)
{
	//int Random(int, int);
	int Partition(int*, int, int);
	int i, temp;
	i = (r -p) / 2; 			// Ramdom(p, r);
	temp = a[p];
	a[p] = a[i];
	a[i] = temp;
	return Partition(a, p, r);
}

void Randomized_Quicksort(int* a, int p, int r)
{
	int q;
	if (p < r)
	{	q = Randomized_Partition(a, p, r);
		Randomized_Quicksort(a, p, q);
		Randomized_Quicksort(a, q + 1, r);
	}
}

int Random(int lower, int upper)
{
	return (int)((float)rand() / RAND_MAX * (upper - lower)) + lower;
}
*/




// this is for the quick sort original