Создание состязательного ввода для сортировок STL [закрыто] ⇐ C++

[Anonymous]

Я обнаружил враждебные входные данные для std::sort, глядя на визуализацию этой перестановки. Идея состоит в том, чтобы позволить алгоритмам STL вызывать std::partial_sort в подмассиве, и мы хотим, чтобы подмассив был как можно более длинным (для случайных входных данных эти алгоритмы редко делают это). Код алгоритма генерации следующий:

Код: Выделить всё

void generate(std::vector& arr) {
for (size_t i = 0; i < arr.size(); i++) arr[i] = i + 1;
size_t i = 4, j = arr.size() - 1;
while (i < j) {
std::swap(arr[i], arr[j]);
i += 2;
j -= 2;
}
std::swap(arr[0], arr[arr.size() - 1]);
}

Согласно моему тесту, он помещает как GCC std::sort, так и MSVC std::sort в случай сортировки кучи. В следующей таблице показано время процессора (

Код: Выделить всё

clock()

), счетчик обращений к массиву и счетчик сравнений во времени формата (доступ/сравнение). Критерии: если количество обращений к массиву превышает 3,5*n*log2(n), то мы предполагаем, что алгоритм столкнулся с кучей.



n
GCC (-O3)
MSVC (/O4)




131072
27,023 мс (18566233 / 6889195)
19 мс (8202054 / 3152744)


1048576
158,886 мс (173777132/64573900)
100 мс (78129920/30096638)


16777216
2499,614 мс (3317506540/1234567896)
1774 мс (1498187752/580803613)


134217728
22777,134 мс (29766865113/11086205472)
15704 мс (13527065651/5255846034)



Вопрос: может ли этот массив помещать std::sort в >=5 библиотек в случай пирамидальной сортировки?

Подробнее здесь: https://stackoverflow.com/questions/798 ... -stl-sorts