Признать различные алгоритмы сортировки на основе входных данных и времени выполнения?

Question

Мне дали класс с 5 методами (от sort1 до sort5), которые я не вижу. Предоставляя массив в качестве входных данных для каждого метода, моя задача состоит в том, чтобы наблюдать и находить, какой алгоритм сортировки реализован для каждого метода (пузырьковая сортировка, вставка, выборка, сортировка слиянием или быстрая сортировка).

Я рассчитал продолжительность для массивов с элементами 10k, 20k, 40k, 80k и 100k, каждый в порядке возрастания, убывания и случайного порядка, но я все еще не могу понять это.

Это мой расчет времени

sort1 ascen 10000 array (0.06400000 seconds)
sort1 ascen 20000 array (0.21700000 seconds)
sort1 ascen 40000 array (0.87100000 seconds)
sort1 ascen 80000 array (3.52100000 seconds)
sort1 ascen 100000 array (5.12500000 seconds)


sort1 dscen 10000 array (0.28900000 seconds)
sort1 dscen 20000 array (1.08200000 seconds)
sort1 dscen 40000 array (4.40100000 seconds)
sort1 dscen 80000 array (17.32000000 seconds)
sort1 dscen 100000 array (27.01900000 seconds)

sort1 random 10000 array (0.28100000 seconds)
sort1 random 20000 array (1.09300000 seconds)
sort1 random 40000 array (4.36800000 seconds)
sort1 random 80000 array (17.48700000 seconds)
sort1 random 100000 array (27.43300000 seconds)



sort2 ascen 10000 array (0.00300000 seconds)
sort2 ascen 20000 array (0.00200000 seconds)
sort2 ascen 40000 array (0.00300000 seconds)
sort2 ascen 80000 array (0.00200000 seconds)
sort2 ascen 100000 array (0.00300000 seconds)


sort2 dscen 10000 array (0.25700000 seconds)
sort2 dscen 20000 array (0.95800000 seconds)
sort2 dscen 40000 array (3.49500000 seconds)
sort2 dscen 80000 array (13.96100000 seconds)
sort2 dscen 100000 array (21.88800000 seconds)


sort2 random 10000 array (0.06100000 seconds)
sort2 random 20000 array (0.29000000 seconds)
sort2 random 40000 array (1.38100000 seconds)
sort2 random 80000 array (6.08200000 seconds)
sort2 random 100000 array (9.78800000 seconds)



sort3 ascen 10000 array (0.00500000 seconds)
sort3 ascen 20000 array (0.00100000 seconds)
sort3 ascen 40000 array (0.00900000 seconds)
sort3 ascen 80000 array (0.01900000 seconds)
sort3 ascen 100000 array (0.04800000 seconds)

sort3 dscen 10000 array (0.00700000 seconds)
sort3 dscen 20000 array (0.88100000 seconds)
sort3 dscen 40000 array (0.03000000 seconds)
sort3 dscen 80000 array (0.04100000 seconds)
sort3 dscen 100000 array (0.00600000 seconds)


sort3 random 10000 array (0.00200000 seconds)
sort3 random 20000 array (0.28400000 seconds)
sort3 random 40000 array (0.00700000 seconds)
sort3 ranodm 80000 array (0.01300000 seconds)
sort3 random 100000 array (0.01800000 seconds)


sort4 ascen 10000 array (0.01200000 seconds)
sort4 ascen 20000 array (0.01100000 seconds)
sort4 ascen 40000 array (0.00300000 seconds)
sort4 ascen 80000 array (0.09800000 seconds)
sort4 ascen 100000 array (0.05100000 seconds)

sort4 dscen 10000 array (0.00700000 seconds)
sort4 dscen 20000 array (0.00900000 seconds)
sort4 dscen 40000 array (3.50300000 seconds)
sort4 dscen 80000 array (0.00900000 seconds)
sort4 dscen 100000 array (0.01600000 seconds)



sort4 random 10000 array (0.00200000 seconds)
sort4 random 20000 array (0.00400000 seconds)
sort4 random 40000 array (1.37300000 seconds)
sort4 random 80000 array (0.01800000 seconds)
sort4 random 100000 array (0.02200000 seconds)



sort5 ascen 10000 array (0.00200000 seconds)
sort5 ascen 20000 array (0.00100000 seconds)
sort5 ascen 40000 array (0.00500000 seconds)
sort5 ascen 80000 array (0.00300000 seconds)
sort5 ascen 100000 array (0.00300000 seconds)


sort5 dscen 10000 array (0.25400000 seconds)
sort5 desc 20000 array (0.86900000 seconds)
sort5 desc 40000 array (3.53500000 seconds)
sort5 desc 80000 array (14.00900000 seconds)
sort5  desc 100000 array (21.85400000 seconds)



sort5 random 10000 array (0.28700000 seconds)
sort5 random 20000 array (1.28500000 seconds)
sort5 random 40000 array (5.84900000 seconds)
sort5 random 80000 array (25.92500000 seconds)
sort5  random  100000 array (41.10800000 seconds)

Answer 1

На первый взгляд, я бы сказал, что у вас нет времени в нескольких случаях. Например, восхождение sort4 для 40000 элементов занимает в 50 раз больше времени, чем для 100000. В ваших данных есть несколько схожих случаев.

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

Затем вы учитываете наилучший и наихудший варианты поведения этих алгоритмов. Например, сортировка выбора должна иметь почти одинаковое время выполнения во всех трех случаях (по возрастанию, по убыванию и случайным образом). Пузырьковая сортировка и сортировка вставок имеют очень хорошее поведение в лучшем случае (по возрастанию). Сортировка слиянием имеет довольно стабильное время выполнения во всех трех случаях. Наивная быстрая сортировка имеет ужасное восходящее или нисходящее поведение, но обычно является самой быстрой для случайного списка.

Вся идея состоит в том, чтобы проверить ваше понимание поведения различных алгоритмов сортировки.