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


int change = 0;
int comp = 0;


int compare(double first, double sec)                                                     //операция сравнения без учета знака
{
    comp++;
    if (fabs(first) > fabs(sec))
        return -1;
    else if (fabs(first) == fabs(sec))
        return 0;
    else return 1;
}


void chan(double *first, double *sec)                                                    //меняем переменные местами
{
    change++;
    double prom = *first;
    *first = *sec;
    *sec = prom;
}


void bubble_sort(double *lst, int n)
{
    for(int i = 0 ; i < n - 1; i++) {
       for(int j = 0 ; j < n - i - 1 ; j++) {
           if(compare(lst[j], lst[j+1]) == -1) {                                          // сравниваем два соседних элемента
              chan(lst + j, lst + j + 1);                                                 // если они идут в неправильном порядке, то меняем их местами
           }
        }
    }
}



void quick_sort(double *lst, int first, int last)
{
    if (first < last)
    {
        int left = first, right = last;
        double middle = lst[(left + right) / 2];
        do
        {
            while (compare(lst[left], middle) == 1) left++;                                // пока не наткнемся на больший/меньший элемент, двигаем указатель
            while (compare(lst[right], middle) == -1) right--;
            if (left <= right)                                                             // если границы поменялись местами
            {
                if (left != right)                                                         // то меняем местами
                    chan(lst + left, lst + right);
                left++;
                right--;
            }
        } while (left <= right);
        quick_sort(lst, first, right);                                                     // запускаем алгоритм на не отсортированных частях
        quick_sort(lst, left, last);
    }
}

void qck_sort(double *lst, int n)
{
    quick_sort(lst, 0, n - 1);
}

void check_compare(double *first, double *sec, int n)
{
    for (int i = 0; i < n; i++)
        if (first[i] != sec[i]) printf("error");
}

void check(double *lst, int n)
{
    for (int i = 0; i < n-1; i++)
        if (fabs(lst[i]) > fabs(lst[i + 1])) printf("error");
}


void generation(void)
{
    srand(time(NULL));
    FILE * bubble = fopen ("bubble.txt", "w");
    FILE * quick = fopen ("quick.txt", "w");


    for (int i = 1; i <= 10; i++)
    {                                                                                    //создание 2 массивов, удовлетворяющих условию
        for (int j = 1; j <= 4; j++)
        {
            double *lst = (double *) malloc(sizeof(double) * i);
            if (j == 1)                                                                  //в прямом порядке
            {
                lst[0] = (double)rand()/(double)(RAND_MAX / 10000);
                for (int k = 1; k < i; k++)
                    lst[k] = lst[k - 1] + (double)rand()/(double)(RAND_MAX / 10000);
            }
            else if (j == 2)                                                             //в обратном порядке
            {
                lst[0] = -1000000000 - (double)rand()/(double)(RAND_MAX / 10000);
                for (int k = 1; k < i; k++)
                    lst[k] = lst[k - 1] + (double)rand()/(double)(130 / 100);
            }
            else                                                                         //произвольном порядке
            {
            for (int k = 0; k < i; k++)
                lst[k] = -5000 + (double)rand()/(double)(RAND_MAX / 10000);
            }

            double *lst2 = (double *) malloc(sizeof(double) * i);
            for (int k = 0; k < i; k++)
                lst2[k] = lst[k];

            bubble_sort(lst, i);
            fprintf(bubble, "bubble: count = %d, number = %d, compares = %d, changes = %d\n", i, j, comp, change);
            change = 0;
            comp = 0;

            /*
            for (int k = 0; k < i; k++)
                printf("%lf ", lst[k]);
            printf("\n");
            printf("_\n");
            printf("_\n");
            */

            qck_sort(lst2, i);
            fprintf(quick, "quick: count = %d, number = %d, compares = %d, changes = %d\n", i, j, comp, change);

            /*
            for (int k = 0; k < i; k++)
                printf("%lf ", lst2[k]);
            printf("\n");
            printf("*\n");
            printf("*\n");
            */

            check(lst, i);                                                          //проверка
            check(lst2, i);
            check_compare(lst, lst2, i);

            change = 0;
            comp = 0;

            free(lst);
            free(lst2);
        }
        fprintf(bubble, "\n");
        fprintf(quick, "\n");
    }
    fclose(bubble);
    fclose(quick);
}


void tests_b(void)                                                                                  //тесты для примера
{
    printf("bubble sort\n");

    double first[10] = {1.4, 2.8, 3.6, 4.1, 5.3, 6.8, 7.4, 8.5, 9.9, 10.8};
    bubble_sort(first, 10);
    for (int k = 0; k < 10; k++)
        printf("%lf ", first[k]);
        printf("\n");

    double sec[10] = {10.8, 9.9, 8.5, 7.4, 6.8, 5.3, 4.1, 3.6, 2.8, 1.4};
    bubble_sort(sec, 10);
    for (int k = 0; k < 10; k++)
        printf("%lf ", sec[k]);
        printf("\n");

    double third[10] = {-1.4, -2.8, -3.6, -4.1, -5.3, -6.8, -7.4, -8.5, -9.9, -10.8};
    bubble_sort(third, 10);
    for (int k = 0; k < 10; k++)
        printf("%lf ", third[k]);
        printf("\n");

    double four[10] = {-10.8, -9.9, -8.5, -7.4, -6.8, -5.3, -4.1, -3.6, -2.8, -1.4};
    bubble_sort(four, 10);
    for (int k = 0; k < 10; k++)
        printf("%lf ", four[k]);
        printf("\n");

    double fith[11] = {3.6, 4.1, 5.3, 2.8, 6.8, 10.8, 7.4, 8.5, 1.4, 10.8, 9.9};
    bubble_sort(fith, 11);
    for (int k = 0; k < 11; k++)
        printf("%lf ", fith[k]);
        printf("\n");

    double six[11] = {-3.6, -4.1, -5.3, -2.8, -6.8, -10.8, -7.4, -8.5, -1.4, -10.8, -9.9};
    bubble_sort(six, 11);
    for (int k = 0; k < 11; k++)
        printf("%lf ", six[k]);
        printf("\n");

    double seven[10] = {-1.4, 2.8, -3.6, 4.1, -5.3, 6.8, -7.4, 8.5, -9.9, 10.8};
    bubble_sort(seven, 10);
    for (int k = 0; k < 10; k++)
        printf("%lf ", seven[k]);
        printf("\n");

    double eight[10] = {-10.8, 9.9, -8.5, 7.4, -6.8, 5.3, -4.1, 3.6, -2.8, 1.4};
    bubble_sort(eight, 10);
    for (int k = 0; k < 10; k++)
        printf("%lf ", eight[k]);
        printf("\n");

    double nine[11] = {3.6, -4.1, -5.3, 2.8, -6.8, 10.8, -7.4, 8.5, -1.4, -10.8, 9.9};
    bubble_sort(nine, 11);
    for (int k = 0; k < 11; k++)
        printf("%lf ", nine[k]);
        printf("\n");

    double ten[11] = {-3.6, 4.1, 5.3, 2.8, -6.8, 10.8, 7.4, -8.5, -1.4, 10.8, -9.9};
    bubble_sort(ten, 11);
    for (int k = 0; k < 11; k++)
        printf("%lf ", ten[k]);
        printf("\n");

    printf("\n");
    printf("\n");

}


void tests_q(void)
{
    printf("quick sort\n");

    double first[10] = {1.4, 2.8, 3.6, 4.1, 5.3, 6.8, 7.4, 8.5, 9.9, 10.8};
    qck_sort(first, 10);
    for (int k = 0; k < 10; k++)
        printf("%lf ", first[k]);
        printf("\n");

    double sec[10] = {10.8, 9.9, 8.5, 7.4, 6.8, 5.3, 4.1, 3.6, 2.8, 1.4};
    qck_sort(sec, 10);
    for (int k = 0; k < 10; k++)
        printf("%lf ", sec[k]);
        printf("\n");

    double third[10] = {-1.4, -2.8, -3.6, -4.1, -5.3, -6.8, -7.4, -8.5, -9.9, -10.8};
    qck_sort(third, 10);
    for (int k = 0; k < 10; k++)
        printf("%lf ", third[k]);
        printf("\n");

    double four[10] = {-10.8, -9.9, -8.5, -7.4, -6.8, -5.3, -4.1, -3.6, -2.8, -1.4};
    qck_sort(four, 10);
    for (int k = 0; k < 10; k++)
        printf("%lf ", four[k]);
        printf("\n");

    double fith[11] = {3.6, 4.1, 5.3, 2.8, 6.8, 10.8, 7.4, 8.5, 1.4, 10.8, 9.9};
    qck_sort(fith, 11);
    for (int k = 0; k < 11; k++)
        printf("%lf ", fith[k]);
        printf("\n");

    double six[11] = {-3.6, -4.1, -5.3, -2.8, -6.8, -10.8, -7.4, -8.5, -1.4, -10.8, -9.9};
    qck_sort(six, 11);
    for (int k = 0; k < 11; k++)
        printf("%lf ", six[k]);
        printf("\n");

    double seven[10] = {-1.4, 2.8, -3.6, 4.1, -5.3, 6.8, -7.4, 8.5, -9.9, 10.8};
    qck_sort(seven, 10);
    for (int k = 0; k < 10; k++)
        printf("%lf ", seven[k]);
        printf("\n");

    double eight[10] = {-10.8, 9.9, -8.5, 7.4, -6.8, 5.3, -4.1, 3.6, -2.8, 1.4};
    qck_sort(eight, 10);
    for (int k = 0; k < 10; k++)
        printf("%lf ", eight[k]);
        printf("\n");

    double nine[11] = {3.6, -4.1, -5.3, 2.8, -6.8, 10.8, -7.4, 8.5, -1.4, -10.8, 9.9};
    qck_sort(nine, 11);
    for (int k = 0; k < 11; k++)
        printf("%lf ", nine[k]);
        printf("\n");

    double ten[11] = {-3.6, 4.1, 5.3, 2.8, -6.8, 10.8, 7.4, -8.5, -1.4, 10.8, -9.9};
    qck_sort(ten, 11);
    for (int k = 0; k < 11; k++)
        printf("%lf ", ten[k]);
        printf("\n");

    printf("\n");
}


int main(void)
{
    generation();
    tests_b();
    tests_q();
    return 0;
}