LABA_1

#include <stdlib.h>
#include <conio.h>
#include <locale.h>
#include <time.h>
#include <iostream>
#include <windows.h>

int assignment=0, comparison=0; //присвоение, срвнение
long int start, res;
//--Создает и заполняет массив указанной длины числами от 0 до 100--//--//
int* randomArr(int n){
	srand(((unsigned)time(0)/2));
	int* arr = (int*)malloc(sizeof(int)*n);
	for(int i=0; i<n; i++){
		arr[i] = rand() % 100;
	}
	return arr;
}
//--Создает и заполняет массив указанной длины случайными числами по возврастаию--//--//
int* randomArrIncr(int n){
	srand(((unsigned)time(0)/2));
	int* arr = (int*)malloc(sizeof(int)*n);
	
	arr[0] = rand() % n - n*3;
	for(int i=1; i<n; i++){
		arr[i] = arr[i-1] + (rand() % 10) +1;
	}
	return arr;
}
//--Создает и заполняет массив указанной длины случайными числами по убыванию--//--//
int* randomArrDecr(int n){
	srand(((unsigned)time(0)/2));
	int* arr = (int*)malloc(sizeof(int)*n);
	
	arr[0] = rand() % n*2 + n;
	for(int i=1; i<n; i++){
		arr[i] = arr[i-1] - (rand() % 10);
	}
	return arr;
}
//----||----||----||----||----||----||----||----||----//

//--Сортировка пузырьком--//--//
void bubbleSort(int* arr, int n){
	//assignment=0, comparison=0;
	//start = GetTickCount();
	int temp;
	comparison++; 
	for(int i=0; i<n; i++){
		comparison++; 
		for(int j=0; j<n-i-1; j++){
			comparison++; 
			if(arr[j] > arr[j+1]){
				temp = arr[j];
				assignment++;
				arr[j] = arr[j+1];
				assignment++;
				arr[j+1] = temp;
				assignment++;
			}
			comparison++; 
		}
		comparison++; 
	}
	//res = GetTickCount() - start;
	
}
//--Сортировка выбором--//--//
void selectSort(int* arr, int n){
	//assignment=0, comparison=0;
	//start = GetTickCount();
	comparison++; 
	for(int i=0; i<n-1; i++){
		int min = i;
		comparison++; 
		for(int j=i+1; j<n; j++){
			comparison++;
			if(arr[j]<arr[min]){
				min = j;
				assignment++;
			}
			comparison++;
		}
		comparison++;
		if(min!=i){
			int temp = arr[min];
			assignment++;
			arr[min] = arr[i];
			assignment++;
			arr[i] = temp;
			assignment++;
		}
		comparison++; 
	}
	
	//res = GetTickCount() - start;
}
//--Сортировка вставками--//--//
void insertSort(int* arr, int n){
	//assignment=0, comparison=0;
	//start = GetTickCount();
	comparison++; 
	for(int i=1; i<n; i++){
		comparison++;
		for(int j=i; j>0 && arr[j-1]>arr[j]; j--){
			int temp = arr[j-1];
			assignment++;
			arr[j-1] = arr[j];
			assignment++;
			arr[j] = temp;
			assignment++;
			
			comparison++; 
		}
		comparison++; 
	}
	//res = GetTickCount() - start;
}
//--Быстрая сортировка--//--//
void quickSort(int* arr, int n){
	int i=0, j=n;
	int temp, p;
	p=arr[n>>1];
	do{
		comparison++; 
		while(arr[i]<p){ i++; comparison++; }
		comparison++; 
		while(arr[j]>p){ j--; comparison++; }
		comparison++; 
		if(i<=j){
			temp = arr[i];
			assignment++;
			arr[i] = arr[j];
			assignment++;
			arr[j] = temp;
			assignment++;
			i++; j--;
		}
		comparison++;
	} while(i<=j);
	comparison++; 
	if(j>0){ quickSort(arr, j); }
	comparison++; 
	if(n>i){ quickSort(arr+i, n-i); }
}

void copyArr(int* arr, int* cArr, int n){
	for(int i=0; i<n; i++) {
		cArr[i] = arr[i];
	}
}

int main(){
	int n, select, *arr, *cArr, iter;
	setlocale(0, "RUSSIAN");
	printf("Введите длину массива: ");
	scanf("%i", &n);
	printf("Выберите способ заполнения массива:\n > 1.По возвраcтанию\n > 2.По убыванию\n > 3.Случайными числами от 1 до 100\n>>: ");
	scanf("%i", &select);
	switch(select){
		case 1:
			arr = randomArrIncr(n);
			break;
		case 2:
			arr = randomArrDecr(n);
			break;
		case 3:
			arr = randomArr(n);
			break;
		default:
			exit(1);
			break;
	}
	cArr = (int*)malloc(sizeof(int)*n);
	while(1){
		printf("arr[%i] = {", n);
		for(int i=0; i<n; i++){
			//printf("%i, ", arr[i]);
		}
		printf("}\n");
		printf("Выберите способ сортировки:\n > 1.Пузырьковая\n > 2.Сортировка выбором\n > 3.Сортировка вставками\n > 4.Быстрая сортировка\n>>: ");
		scanf("%i", &select);
		printf("Введите количество повторений сортировки: ");
		scanf("%i", &iter);
		//if(iter<=0) { exit(1); }
		switch(select){
			case 1:
				assignment=0, comparison=0;
				start = GetTickCount();
				for (int i=0; i<iter; i++) {
					copyArr(arr, cArr, n);
					bubbleSort(cArr, n);
				}
				res = GetTickCount() - start;
				break;
			case 2:
				assignment=0, comparison=0;
				start = GetTickCount();
				for (int i=0; i<iter; i++) {
					copyArr(arr, cArr, n);
					selectSort(cArr, n);
				}
				res = GetTickCount() - start;
				break;
			case 3:
				assignment=0, comparison=0;
				start = GetTickCount();
				for (int i=0; i<iter; i++) {
					copyArr(arr, cArr, n);
					insertSort(cArr, n);
				}
				res = GetTickCount() - start;
				break;
			case 4:
				assignment=0, comparison=0;
				start = GetTickCount();
				for (int i=0; i<iter; i++) {
					copyArr(arr, cArr, n);
					quickSort(cArr, n);
				}
				res = GetTickCount() - start;
				break;
			default:
				exit(1);
				break;
		}
		
		
		printf("arr[%i] = {", n);
		for(int i=0; i<n; i++){
		//	printf("%i, ", cArr[i]);
		}
		printf("}\n");
		printf("\nВремя выполнения: %lf\nКоличество присвоений: %i\nКоличество сравнений: %i\n", (double)res/iter, assignment/iter, comparison/iter);
		getch();
	}
}