task1(OA)

#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <ctime>

using namespace std;

void countSort(int *a, int dif, int min, int n)
{
    int *CountSort = new int[dif];

    for (int i = 0; i < dif; i++)
        CountSort[i] = 0;

    for (int i = 0; i < n; i++)
        CountSort[a[i] - min]++;

    //for (int i = 0; i < dif; i++)
    //    for (int j = 0; j < CountSort[i]; j++)
    //        cout << i + min << " ";
	cout << endl << endl;
}

void dischargeSort(int* a, int n, int max)
{
	int* DischargeSort = new int [n];
	int k = 0;
	int s = 0;
	int num = 1;
	while (max > 0)
	{
		max = max/10;
		k++;
	}

	for (int i = 0; i < k; i++)
	{
		for (int j = 0; j < 10; j++)
		{
			for (int z = 0; z < n; z++)
			{
				if ((a[z]/num)%10 == j)
				{
					DischargeSort[s] = a[z];
					s++;
				}
			}
		}
		num *= 10;
		s = 0;
	}

	//for (int i = 0; i < n; i ++)
	//	cout << DischargeSort[i] << " ";
	//cout << endl << endl;
}

int main()
{
    setlocale(LC_ALL,"RUS");

    int n, max, min;
    cin >> n;

    min = 1000;
    max = -1;

    int *a = new int[n];
    srand ((unsigned int)time(NULL)); // начальная точка генерации
	cout << "Исходный массив" << endl;
    for (int i = 0; i < n; i++)
    {
        a[i] = rand()%100;
        cout << a[i] << " ";
        if (a[i] > max)
            max = a[i];
        if (a[i] < min)
            min = a[i];
    }
	int dif = max - min + 1;
    cout << endl << endl;

	cout << "Сортировка Подсчётом" << endl;
	countSort(a,dif,min,n);

	cout << "Поразрядная сортировка(LSD)" << endl;
	dischargeSort(a,n,max);

	cout << "Оценка сложности" << endl << endl;

	n = 10;
	unsigned int start, end;
	unsigned int* count = new unsigned int [5];
	unsigned int* discharge = new unsigned int [5];
	int s = 0;
	for (int i = 0; i < 5; i++)
	{
		count[i] = 0;
		discharge[i] = 0;
	}

	for (n; n < 1000000; n *= 10)
		cout << n << endl;

	for (n; n < 1000000; n *= 10)
	{
		start = clock();
		countSort(a,dif,min,n);
		end = clock();
		count[s] = end - start;
		s++;
	}

	for (n; n < 1000000; n += 10)
	{
		start = clock();
		dischargeSort(a,n,max);
		end = clock();
		discharge[s] = end - start;
		s++;
	}

	cout << "Сортировка Подсчётом" << endl;
	for (int i = 0; i < 5; i++)
		cout << count[i] << " ";
	cout << endl << endl;

	cout << "Поразрядная сортировка(LSD)" << endl;
	for (int i = 0; i < 5; i++)
		cout << discharge[i] << " ";
	cout << endl << endl;


    system("pause");
}