Вы наткнулись на важное свойство ассимптотического анализа. 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.
