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

#define N1 1000
#define N2 5000
#define N3 10000
#define N4 15000

void in_pmas (int *, int *, int);  //Êîïèè ìàññèâà
void in_mas (int *, int);  //Íåóïîðÿäî÷åííàÿ ïîñëåäàâàòåëüíîñòü
void in_up_mas (int *, int); //Óïîðÿäî÷åííûé ìàññèâ
void in_uo_mas (int *, int); //Óïîðÿäî÷åííûé â îáðàòíîì ïîðÿäêå
void sort (int *, int *, int *, int *, int, int, int, int);   //Ñîðòèðîâêà
int QuickSort (int *, int);
int HeapSort (int *, int n);
int sift (int *, int, int);
int BubbleSort1 (int *, int);
int StraightInsertionSort( int *, int n );
void tab (int *, int); //äëÿ òàáëèöû
int comp (const void *i, const void *j);

int colG=0;

int main()
{
	setlocale( LC_ALL, "rus");
	int i, j;
	int *n1=(int*)malloc(N1 * sizeof(int)), *n2=(int*)malloc(N2 * sizeof(int)), *n3=(int*)malloc(N3 * sizeof(int)), *n4=(int*)malloc(N4 * sizeof(int));
	in_up_mas(n1, N1);
	in_up_mas(n2, N2);
	in_up_mas(n3, N3);
	in_up_mas(n4, N4);
	puts(" _____________________________________________________________________");
    puts("|                     Ìàññèâû â ïðÿìîì ïîðÿäêå                        |");
	sort(n1, n2, n3, n4, N1, N2, N3, N4);
	in_uo_mas(n1, N1);
	in_uo_mas(n2, N2);
	in_uo_mas(n3, N3);
	in_uo_mas(n4, N4);
	puts(" _____________________________________________________________________");
    puts("|                     Ìàññèâû â îáðàòíîì ïîðÿäêå                      |");
	sort(n1, n2, n3, n4, N1, N2, N3, N4);
	in_mas(n1, N1);
	in_mas(n2, N2);
	in_mas(n3, N3);
	in_mas(n4, N4);
	puts(" _____________________________________________________________________");
    puts("|                     Ìàññèâ çàïîëíåííûé ñëó÷àéíûìè ÷èñëàìè           |");
	sort(n1, n2, n3, n4, N1, N2, N3, N4);
	system("pause");
	free(n1);
	free(n2);
	free(n3);
	free(n4);
	return 0;
}

void sort (int *n1, int *n2, int *n3, int *n4, int col1, int col2, int col3, int col4)
{
	int (*f[4])(int *, int) = {StraightInsertionSort, HeapSort, BubbleSort1, QuickSort};
	int *p_n1=(int*)malloc(col1 * sizeof(int)), *p_n2=(int*)malloc(col2 * sizeof(int)), *p_n3=(int*)malloc(col3 * sizeof(int)), *p_n4=(int*)malloc(col4 * sizeof(int));
	int *mas=(int*)malloc(16 * sizeof(int));
	int i, j, k=0;
	for (j=0; j<4; j++)
    {
       	in_pmas (p_n1, n1, col1);
       	in_pmas (p_n2, n2, col2);
       	in_pmas (p_n3, n3, col3);
       	in_pmas (p_n4, n4, col4);
        mas[k]=f[j](p_n1, col1); k++;
        mas[k]=f[j](p_n2, col2); k++;
       	mas[k]=f[j](p_n3, col3); k++;
       	mas[k]=f[j](p_n4, col4); k++;
    }
    tab (mas, k);
    free(mas);
    free(p_n1);
	free(p_n2);
	free(p_n3);
	free(p_n4);
}

void in_pmas (int *p_m, int *m, int n)
{
	int i;
    for (i=0; i<n; i++)
 	 p_m[i]=m[i];
}

void in_mas (int *m, int n)
{
	int i;
	for (i=0; i<n; i++)
	 m[i]=rand()%100;
}

void in_up_mas (int *m, int n)
{
	int i;
	for (i=0; i<n; i++)
	 m[i]=i+1;
}

void in_uo_mas (int *m, int n)
{
	int i;
	for (i=0; i<n; i++)
	 m[i]=n-i;
}

void tab (int *m, int n)
{
	puts("|_____________________________________________________________________|");
	puts("|                           |        |        |           |           |");
	puts("|                           |  1000  |  5000  |   10000   |  15000    |");
	puts("|___________________________|________|________|___________|___________|");
	puts("|                           |        |        |           |           |");
	printf("| Ïðîñòûìè âñòàâêàìè        |%8d|%8d|%11d|%11d|\n", m[0], m[1], m[2], m[3]);
	printf("| Ïèðàìèäàëüíàÿ ñîðò        |%8d|%8d|%11d|%11d|\n", m[4], m[5], m[6], m[7]);
	printf("| Ïóçûðüêîâàÿ ñîðò ñ îãðàíè÷|%8d|%8d|%11d|%11d|\n", m[8], m[9], m[10], m[11]);
	printf("| Áûñòðàÿ ñîðòèðîâêà        |%8d|%8d|%11d|%11d|\n", m[12], m[13], m[14], m[15]);
	puts("|___________________________|________|________|___________|___________|");
	system("pause");
}

/* Áûñòðàÿ ñîðòèðîâêà */
int QuickSort (int *a, int n)
{
	int x, w, i, j, col4=0;
    x = a[n/2];
	i=0; j=n-1;
	do
	{
		while (a[i]<x) i++;
		while (x<a[j]) j--;
		if (i<=j)
		{
			w = a[i]; a[i] = a[j]; a[j] = w;
			i++; j--;
			col4+=3;
		}
	}
	while (i<j);
	//printf("\nÁûñòðàÿ ñîðòèðîâêà, êîë-âî ïåðåñòàíîâîê: %d\n", counter3);
	if (j>0)
		col4+=QuickSort (a, j+1);
	if (i<n-1)
		col4+=QuickSort (a+i, n-i);
		return col4;
}

/* Ïèðàìèäàëüíàÿ ñîðòèðîâêà */
int HeapSort (int *a, int n)
{
	int col2=0, left = n/2+1, right=n-1, x;
	while (left>1)
		col2+=sift (a, --left, right);
	while (right>1)
	{
		x = a[1];
		a[1] = a[right];
		a[right] = x;
		col2+=sift (a, left, --right);
		col2+=3;
	}
	return col2;
}

/* Ïðîñåèâàíèå ñêâîçü ïèðàìèäó */
int sift (int *a, int left, int right)
{
	int i, j, x=a[left],col2=1;
    i = left; j = 2*left;
	if (j<right && a[j+1]<a[j])	//åñëè ýëåìåíò j íå ïîñëåäíèé â ðàññìàòð. ïîñëåäîâàòåëüíîñòè
		j++;		//è ëåâûé áðàò ìåíüøå ïðàâîãî, ïåðåñòàâëÿåì óêàçàòåëü íà íåãî
	while (j<=right && a[j]<x)	//ïðîñìàòðèâàåì ïîòîìêîâ äî êîíöà ïîñëåäîâàòåëüíîñòè,
	{				//åñëè îíè ìåíüøå òåêóùåãî (õ) ýëåìåíòà, ò.å. íàðóøåíà
		a[i] = a[j];	//óïîðÿäî÷åííîñòü ïèðàìèäû, òî âîññòàíàâëèâàåì åå,
		i = j;		//ïîäíèìàÿ ïîòîìêîâ íà óðîâåíü âûøå
		j *= 2;
		col2++;
		if (j<right && a[j+1]<a[j])	//è êàæäûé ðàç âûáèðàåì äëÿ àíàëèçà ìåíüøåãî èç
			j++;			//áðàòüåâ
	}
	a[i] = x;col2++;
	return col2;
}

/* Ïóçûðüêîâàÿ ñîðòèðîâêà ñ îãðàíè÷åíèåì ïðîõîäîâ */
int BubbleSort1 (int *a, int n)
{
	int i, j, x, flag=1, col3=0;
	for (i=1; flag; i++)
	{
		flag = 0;	//ïðèçíàê óïîðÿäî÷åííîé ïîñëåäîâàòåëüíîñòè
		for (j=n-1; j>=i; j--)
			if (a[j]>a[j-1])
			{
				col3+=3;
				x = a[j-1];
				a[j-1] = a[j];
				a[j] = x;
				flag = 1; //áûëà ïåðåñòàíîâêà, çíà÷èò, åùå íå âñå
			}
	}
	return col3;
}

/* Ñîðòèðîâêà âñòàâêàìè
int StraightSelection (int* arr,int n)
{
   int counter=0, i, j, tmp;
    for(i=1;i<n;i++){
        for(j=i; j>0 && arr[j-1]<arr[j];j--){
            counter+=3;
            tmp=arr[j-1];
            arr[j-1]=arr[j];
            arr[j]=tmp;
        }
    }
    return counter;
}
*/

/* Ñîðòèðîâêà ïðîñòûìè âñòàâêàìè
int InsertSort(int *mas, int n) //ñîðòèðîâêà âñòàâêàìè
{
	int i, j , key=0, temp=0, counter;
for (i=0; i<n-1; i++)
{
key=i+1;
temp=mas[key];
counter++;
for (j=i+1; j>0 && temp<mas[j-1]; j--)
{

mas[j]=mas[j-1];
key=j-1;
counter++;

}
mas[key]=temp;
counter++;
}
return counter;
}*/

////////

int StraightInsertionSort( int *m, int n )
{
	int x, j, i,col1;
	for( i = 1; i < n; i++ )
     {
       x = m[ i ]; // âñòàâëÿåì ýëåìåíò
       j = i - 1;
                 // Ïîèñê ìåñòà âñòàâêè
       col1+=2;
     while( j != -1 && (x < m[ j ]) )
     {
       m[j+1] = m[j]; //ïåðåìåùåíèå ïðîïóñêàåìîãî ýëåìåíòà âïðàâî
       j--;
     }

       m[ j + 1 ] = x; // Ýëåìåíò çàïîëíÿåò îñâîáîäèâøååñÿ ìåñòî
       col1++;
    }
    return col1;
}