#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();
}
}