Как сымитировать правильную скорость выполнения различных сортировок путём usleep?

Question

[Kevsh]

Пишу визуализацию различных сортировок на c++ и SFML. Мне хотелось бы, чтобы выполнение сортировок можно было бы вообще заметить. Также мне хотелось бы, чтобы было видно разницу и сходство времени выполнения между различными сортировками, то есть сортировки вставкой и выбором должны выполняться примерно за одно и то же время на одном и том же массиве. Я искусственно замедляю сортировки, вот пример:

void selection_sort (elem a[], int size)
{
    int min = a[0].value, min_index;
    
    for (int i = 0 ; i < size; i++)
    {
        min_index = i; usleep(90);
        min = a[i].value; usleep(90);
        for (int j = i; j < size; j++)
        {
            usleep(90);
            if (a[j].value< min)
            {
                min = a[j].value; usleep(90);
                min_index = j; usleep(90);
            }
        }
        swap_elements(a, i, min_index); usleep(90);
    }
}

В книге по алгоритмам, по которой я сейчас учу сортировки, время выполнения рассчитывается исходя из того, что, допустим, строка n, где в массив записывается какое-то число, и строка n + 1, где складываются два числа, могут иметь разное время выполнения. Я же просто везде приостанавливаю выполнение сортировки на фиксированное время. Однако если просто делать это после каждой строки, время выполнения сортировок с одинаковой сложностью различается, причем иногда процентов на 30. Есть ли другие способы замедлить сортировку? Если нет, то как её замедлять более грамотно, чтобы визуализация отображала реальную разницу между сортировками?

Comments

[Alexandroppolus]

то есть сортировки вставкой и выбором должны выполняться примерно за одно и то же время на одном и том же массиве

почему?
если здесь честно "подсвечивается слипом" каждое действие, то всё норм.
разница 30% это вообще чуть ли не совпадение.
у этих сортировок одинакова только асимптотика. К сортировке массива из нескольких десятков элементов это вообще никаким боком - на одних только коэффициентах можно получить куда более ваших несчастных 30%

[Kevsh]

Alexandroppolus, понял, я просто думал, что алгоритмы с одинаковым порядком роста должны выполняться +- с одинаковой скоростью на более менее больших массивах.

Answer 1

[Wataru]

Вы наткнулись на важное свойство ассимптотического анализа. O(n^2) -означает, что на достаточно больших n, время работы будет примерно n^2 с точностью до константы. Эта самая константа может быть хоть 0.5, хоть 10000000.

Сравните 2 алгоритма:

// n(n-1)/2 инкремента.
for(i = 0; i < n; ++i){
  for (j = i+1; j < n; j++) {
    cnt1++;
  }
}
// n^2 инкремента.
for(i = 0; i < n; ++i){
  for (j =0; j < n; j++) {
    cnt2++;
  }
}

Оба алгоритма имеют O(n^2) сложность, но один делает примерно в 2 раза меньше операций.

Суть в том, что хоть алгоритмы и работают с одинаковой ассимптотикой, они могут работать разное время! Особые странности могут быть при маленьких n. O(n log n) алгоритм часто может быть медленнее O(n^2) алгоритма. Поэтому все настоящие реализации сортировок для маленьких массивов запускают более тупые квадратичные алгоритмы.

Если же вы хотите показать только ассимптотику, то возьмите n побольше, и тогда эти 30% будут незаметны по сравнению с десятикратным замедлением O(n^2) относительно O(n log n). Или нормируйте ваши сортировки. Искуственно ускорьте одни алгоритмы и замедлите другие, чтобы получить именно тот результат, который вы хотите. Но это как-то нечестно что ли. Если же вы все-таки хотите именно этого, назначьте каждой сортировке время C\*n^2 или С\*n\*log n миллисекунд. Прогоните алгоритмы сортировки без визуализации, подсчитайте, сколько операций замедления вы бы сделали (тот же самый код, что у вас, только вместо usleep() делайте sleep_count++). В конце подсчитайте коэффициент замедления - сколько каждый usleep должен спать, чтобы суммарно sleep_count их спал заданное время. И запускайте каждую сортировку уже с подсчитанными параметрами для usleep.