#include "sort.h"

void merge_sort_asc(int a[], int p, int r);
void merge_sort_disc(int a[], int p, int r);
void merge_asc(int a[], int p, int q, int r);
void merge_disc(int a[], int p, int q, int r);
void q_sort_asc(int v[], int l, int r);
void q_sort_disc(int v[], int l, int r);

void i_sort(int v[], int n, int dir) {

	int i, j, key;

	if (dir>=0) {		/* il test sul verso lo effettuo solo 1 volta */
		for(j=1; j<n; j++) {
			key = v[j];
			i = j-1;
			while((i>=0)&&(v[i]>key)) {
				v[i+1] = v[i];
				i--;
			}
			v[i+1] = key;
		}
	}
	else {			/* ordinamento decrescente */
		for(j=1; j<n; j++) {
			key = v[j];
			i = j-1;
			while((i>=0)&&(v[i]<key)) {
				v[i+1] = v[i];
				i--;
			}
			v[i+1] = key;
		}
	}
}	/* end of ISORT */


void m_sort(int v[], int n, int dir) {
	if (dir>=0)
		merge_sort_asc(v, 0, n-1);
	else
		merge_sort_disc(v, 0, n-1);
}

void merge_sort_asc(int a[], int p, int r) {
	int q;
	if (p<r) {
		q = (p+r)/2;
		merge_sort_asc(a, p, q);
		merge_sort_asc(a, q+1, r);
		merge_asc(a, p, q, r);
	}
}

void merge_sort_disc(int a[], int p, int r) {
	int q;
	if (p<r) {
		q = (p+r)/2;
		merge_sort_disc(a, p, q);
		merge_sort_disc(a, q+1, r);
		merge_disc(a, p, q, r);
	}
}

void merge_asc(int a[], int p, int q, int r) {
	int temp[MAX_DIM], i, n1, n2;
	n1 = p;
	n2 = q+1;
	for(i=0; i<=(r-p); i++) {
		if ((n1<=q)&&(n2<=r)) {		/* entrambi i vettori non sono terminati */
			if (a[n1]<a[n2]) {
				temp[i] = a[n1];
				n1++;
			}
			else {
				temp[i] = a[n2];
				n2++;
			}
		}
		else {				/* almeno 1 vettore è terminato */
			if (n1<=q) {		/* è terminato il secondo vettore (n2>r) */
				temp[i] = a[n1];
				n1++;
			}
			else {			/* è terminato il primo vettore (n1>q) */
				temp[i] = a[n2];
				n2++;
			}
		}
	}	/* end of FOR */
	for(i=0; i<=(r-p); i++) 		/* copia del vettore temporaneo */
		a[p+i] = temp[i];
}

void merge_disc(int a[], int p, int q, int r) {
	int temp[MAX_DIM], i, n1, n2;
	n1 = p;
	n2 = q+1;
	for(i=0; i<=(r-p); i++) {
		if ((n1<=q)&&(n2<=r)) {		/* entrambi i vettori non sono terminati */
			if (a[n1]>a[n2]) {
				temp[i] = a[n1];
				n1++;
			}
			else {
				temp[i] = a[n2];
				n2++;
			}
		}
		else {				/* almeno 1 vettore è terminato */
			if (n1<=q) {		/* è terminato il secondo vettore (n2>r) */
				temp[i] = a[n1];
				n1++;
			}
			else {			/* è terminato il primo vettore (n1>q) */
				temp[i] = a[n2];
				n2++;
			}
		}
	}	/* end of FOR */
	for(i=0; i<=(r-p); i++) 		/* copia del vettore temporaneo */
		a[p+i] = temp[i];
}


void q_sort(int v[], int n, int dir) {
	if (dir>=0)
		q_sort_asc(v, 0, n-1);
	else
		q_sort_disc(v, 0, n-1);
}

void q_sort_asc(int v[], int l, int r) {
	int i, last;
	void swap(int v[], int i, int j);
	if (l>=r) return;	/* se il vettore contiene meno di 2 elementi non si fa nulla */
	/* Sposta l'elemento discriminante in v[l] */
	swap(v, l, (l+r)/2);
	last = l;
	for(i=l+1; i<=r; i++)
		if (v[i]<v[l]) swap(v, ++last, i);
	/* Ripristina l'elemento discriminante */
	swap(v, l, last);
	q_sort_asc(v, l, last-1);
	q_sort_asc(v, last+1, r);
}

void q_sort_disc(int v[], int l, int r) {
	int i, last;
	void swap(int v[], int i, int j);
	if (l>=r) return;	/* se il vettore contiene meno di 2 elementi non si fa nulla */
	/* Sposta l'elemento discriminante in v[l] */
	swap(v, l, (l+r)/2);
	last = l;
	for(i=l+1; i<=r; i++)
		if (v[i]>v[l]) swap(v, ++last, i);
	/* Ripristina l'elemento discriminante */
	swap(v, l, last);
	q_sort_disc(v, l, last-1);
	q_sort_disc(v, last+1, r);
}

void swap(int v[], int i, int j) {
	int temp;
	temp = v[i];
	v[i] = v[j];
	v[j] = temp;
}