day4

#include <iostream>
#include <algorithm>


int random(int N)
{
    return rand() % N;
}

int B_qunter = 0;
int C_qunter = 0;


void Qsort(int A[],int first, int last)
{
    int L, R, vr, X;
    if (first < last)
    {
        X = A[(last + first) / 2];
        L = first; R = last;
        while (L <= R)
        {
            while (A[L] > X) L++;
            while (A[R] < X) R--;
            if (L <= R) {
                vr = A[L];
                A[L] = A[R];
                A[R] = vr;
                L++; R--;
            }
        }
        Qsort(A, first, R);
        Qsort(A, L, last);
    }
}
void Qsort_with_qunter(int B[], int first, int last)
{
    int L, R, vr, X;
    if (first < last)
    {
        X = B[(last + first) / 2];
        L = first; R = last;
        while (L <= R)
        {
            while (B[L] > X) L++;
            while (B[R] < X) R--;
            if (L <= R) {
                B_qunter++;
                vr = B[L];
                B[L] = B[R];
                B[R] = vr;
                L++; R--;
            }

        }

            Qsort_with_qunter(B, first, R);

            Qsort_with_qunter(B, L, last);
    }
}

int main()
{
    setlocale(LC_ALL, "Russian");
    srand(time(0));

    int B[500];
    int C[500];

    int A[10];

    int flag;
    int vr;
    printf("Задание 1\n");

    printf("Исходный массив\n");
    for (int i = 0; i < 10; i++)
    {
        A[i] = random(101);
        printf("%d ", A[i]);
    }
    printf("\n");

    int i = 0;
    do {
        flag = 0; // сбросить флаг
        for (int j = 8; j >= i; j--)
            if (A[j]%10 > A[j + 1]%10) {
                vr = A[j];
                A[j] = A[j + 1];
                A[j + 1] = vr;
                flag = 1; // поднять флаг
            }
        i++;
    } while (flag);

    printf("Результат\n");
    for (int i = 0; i < 10; i++)
    {
        printf("%d ", A[i]);
    }


    ///////////////////////////////////////////////////

    printf("\n\n\nЗадание 2\n");
    printf("Исходный массив\n");

    for (int i = 0; i < 10; i++)
    {
        A[i] = random(101);
        printf("%d ", A[i]);
    }
    printf("\n");

    i = 0;
    do {
        flag = 0;
        for (int j = 3; j >= i; j--)
        {
            if (A[j] > A[j + 1])
            {

                vr = A[j];
                A[j] = A[j + 1];
                A[j + 1] = vr;
                flag = 1;
            }
        }
        i++;
    } while (flag);

    i = 5;
    do {
        flag = 0;
        for (int j = 8; j >= i; j--)
        {
            if (A[j] < A[j + 1])
            {

                vr = A[j];
                A[j] = A[j + 1];
                A[j + 1] = vr;
                flag = 1;
            }
        }
        i++;
    } while (flag);

    printf("Результат\n");
    for (int i = 0; i < 10; i++)
    {
        printf("%d ", A[i]);
    }

    ///////////////////////////
    printf("\n\n\nЗадание 3\n");
    printf("Исходный массив\n");

    for (int i = 0; i < 10; i++)
    {
        A[i] = random(101);
        printf("%d ", A[i]);
    }
    printf("\n");

    int qunter = 0;
    for (int i = 0; i < 10; i++)
    {
        if (A[i] % 100 < 10)
            qunter++;
    }

    int* array_0dec;
    array_0dec = new int[qunter];


    for (int i = 0,j=0; i < 10; i++)
    {
        if (A[i] % 100 < 10)
        {
            array_0dec[j] = A[i];
            j++;
        }
    }

    printf("Результат\n");
    for (int i = 0; i < qunter; i++)
    {
        printf("%d ", array_0dec[i]);
    }

    ///////////////////////////
    printf("\n\n\nЗадание 4\n");
    printf("Исходный массив\n");

    for (int i = 0; i < 10; i++)
    {
        A[i] = random(101);
        printf("%d ", A[i]);
    }
    printf("\n");

    Qsort(A,0, 10);

    printf("Результат\n");
    for (int i = 0; i < 10; i++)
    {
        printf("%d ", A[i]);
    }

    ///////////////////////////
    printf("\n\n\nЗадание 5\n");
    for (int i = 0; i < 500; i++)
    {
        vr = random(101);
        B[i] = vr;
        C[i] = vr;
    }

    for (int i = 0; i < 499; i++) {
        for (int j = 498; j >= i; j--)
            if (C[j] > C[j + 1]) {
                vr = C[j];
                C[j] = C[j + 1];
                C[j + 1] = vr;
                C_qunter++;
            }
    }
    //qsortRecursive(B, 500);
    Qsort_with_qunter(B, 0, 500);

    printf("Количество методом «пузырька» %d,  методом «быстрой сортировки» %d\n\n", C_qunter,B_qunter);
}