Определить значение M и зависит ли M от k?

Question

Вот упражнение, которое я борюсь с:

Один из способов улучшить производительность QuickSort является переключение на сортировку вставок, когда субфайловые имеют < = M элементов вместо рекурсивного вызова себя.

Внедрение рекурсивного QuickSort с отсечкой для InsertionSort для подфайлов с M или менее элементами. Эмпирически определите значение M, для которого он выполняет наименьшее количество ключевых сравнений на входах 60000 случайных натуральных чисел, меньших K, для K = 10 100 000, 10000, 100000, 1000000. Соответствует ли оптимальное значение M K?

Моих вопросов: Я хотел бы знать, отличается ли значение М из утверждения 1 и ведомость 3. Если да, то что бы размер массива, и как изменить случайные числа? Как сравнить M и K? У меня есть математическое уравнение, или я должен просто делать это с помощью моего кода?

Answer 1

1. Решите сортировку сортировки в соответствии с запросом.
2. Добавить поддержку для записи количества сравнений (например, increment a global)
3. Создайте 5 наборов входных данных для каждого k. Так что 30 файлов с 1 800 000 строк.
4. Запустите сортировку на каждом наборе для каждого K и предположите M пару раз. Начните с низкоценных входных данных и создайте благоприятные M, чтобы ваши догадки продвигались к высокоценным входам.
5. Опишите свои наблюдения о влиянии М над К.
6. Пропустите упражнение как про