Нахождение момента временни, при котором radixSort начинает быстрее сортировать чем quickSort

[shonzie]

Код:

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cmath>
using namespace std;

const unsigned int ARRSIZE = 1000000;
const int DIGITRANGE = 10;
const int MIN = 0;
const int MAX = 10;

void swap(int &fnum, int &snum) {
int tmp = fnum;
fnum = snum;
snum = tmp;
}
int randRange(int min, int max) {
return rand() % (max + 1 - min) + min;
}
int maxDigits(int arr[]) {
int max = 0;
for (int i = 1; i < ARRSIZE; i++) {
if (arr[i] > arr[max])
max = i;
}
int num = arr[max];
int cnt = 0;
while (num > 0) {
cnt++;
num = num / 10;
}
return cnt;
}
void countingSortExp(int arr[], int exp) {
int *counters_arr = new int[DIGITRANGE];
int *sorted_arr = new int[ARRSIZE];
for (int key = 0; key < DIGITRANGE; key++)
counters_arr[key] = 0;
for (int i = 0; i < ARRSIZE; i++)
counters_arr[(arr[i] / exp) % 10]++;
for (int key = 1; key < DIGITRANGE; key++)
counters_arr[key] += counters_arr[key - 1];
for (int i = ARRSIZE - 1; i >= 0; i--) {
counters_arr[(arr[i] / exp) % 10]--;
sorted_arr[counters_arr[(arr[i] / exp) % 10]] = arr[i];
}
for (int i = 0; i < ARRSIZE; i++)
arr[i] = sorted_arr[i];
delete [] counters_arr;
delete [] sorted_arr;
}
void radixSort(int arr[]) {
int exp = 1;
int digits = maxDigits(arr);
while (exp <= pow(10, digits)) {
countingSortExp(arr, exp);
exp *= 10;
}
}
int partition(int arr[], int left, int right) {
int split_point = left - 1;
for (int j = left; j < right; j++) {
if (arr[j] <= arr[right]) {
split_point++;
swap(arr[split_point], arr[j]);
}
}
swap(arr[split_point + 1], arr[right]);
return split_point + 1;
}
int randomizedPartition(int arr[], int left, int right) {
int rand = randRange(left, right);
swap(arr[rand], arr[right]);
return partition(arr, left, right);
}
void quickSortHoare(int arr[], int left, int right) {
if (left < right) {
int split_point = randomizedPartition(arr, left, right);
quickSortHoare(arr, left, split_point - 1);
quickSortHoare(arr, split_point + 1, right);
}
}

int main () {
srand(time(NULL));
int *arr1 = new int[ARRSIZE];
int *arr2 = new int[ARRSIZE];
clock_t start;
double duration;

for (int i = 0; i < ARRSIZE; i++) {
arr1[i] = randRange(MIN, MAX);
arr2[i] = arr1[i];
}

start = clock();
radixSort(arr1);
duration = ( clock() - start ) / (double) CLOCKS_PER_SEC;
cout << duration << " (Radix)" << endl;
delete [] arr1;

start = clock();
quickSortHoare(arr2, 0, ARRSIZE - 1);
duration = ( clock() - start ) / (double) CLOCKS_PER_SEC;
cout << duration << " (Quick)" << endl;

delete [] arr2;
/*
for (int i = 0; i < ARRSIZE; i++)
cout << arr1[i] << " ";
cout << endl;
for (int i = 0; i < ARRSIZE; i++)
cout << arr2[i] << " ";
cout << endl;
*/

return 0;
}

Проблема:
Нужно найти некоторое время n0, при котором происходит смена темпа роста функций radixSort и quickSort. Известно, что quickSort имеет асимптотическйи прирост, а radixSort линейный, так как это соответственно О(logn * n) и О(n) функции. Сначала кривая QS
исгибается, т.е. лежит ниже линейной, а после некоторого n0 - линейная ниже. Каким образом возможно найти это n0, например для цифр ?

[New man]

Ну, это довольно нечёткая граница.

В одном измерении может быть один результат, в другом совсем другой.

[New man]

А вообще, вот тебе идея.
Мы знаем асимптотику каждого алгоритма.
Ну, значит, можем найти константу C для него, просто запуская на больших n.

T1 = С1*n
T2 = C2*n*log(n)

Мы можем приравнять:
C1*n = C2*n*logn <=> C1/C2 = log n

[shonzie]

Благодраю!