что такое обрезанное значение в алгоритмах сортировки?

Question

Меня попросили сделать быструю сортировку, отрезанную с помощью сортировки вставкой.Но я не понял смысла обрезанного значения.Мне нужен кто-то, кто разработает эту концепцию на реальных примерах.

Answer 1

Некоторые алгоритмы асимптотически лучше, чем другие.В вашем случае асимптотическое время выполнения быстрой сортировки равно O (N (logN)), тогда как асимптотическое время выполнения сортировки вставки равно O (N ^ 2).

Это означает, что для больших значений N, быстрая сортировкабудет работать быстрее, чем сортировка вставкой.

Однако при небольших значениях N сортировка вставки может выполняться быстрее.Следовательно, вы можете оптимизировать фактическое время выполнения Quicksort, комбинируя его с сортировкой вставок для небольших размеров массива.

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

Answer 2

Трудно быть уверенным, не видя точного изложения требований.

Однако я думаю, что это означает, что вы должны использовать сортировку вставок (O(N^2)) ниже определенного размера («обрезать») и быструю сортировку (O(NlogN)) выше этого размера.

• Они могут означать, что вы выполняете этот тест для размера входного массива.

• Они также могут означать, что вы реализуете гибридную сортировку и используете вставкусортировка по подмассиву, когда размер раздела быстрой сортировки меньше порогового значенияКонцепция с реальными примерами.

  Я сомневаюсь, что вам нужны примеры, чтобы понять это.Если вы понимаете алгоритмы сортировки вставкой и быстрой сортировки, то это концептуально просто.(И если вы не понимаете их, есть много мест, где о них можно прочитать, начиная с вашего учебника по структурам данных и алгоритмам.)