#sorting #quicksort
#сортировка #быстрая сортировка
Вопрос:
Я ненавижу просто публиковать вопрос о домашнем задании, но у меня много проблем с тем, что они пытаются спросить у меня. Я не прошу вас решать мою домашнюю задачу, только чтобы указать мне первые шаги, которые я должен предпринять, потому что я не знаю, с чего начать. Я прочитал часть главы о быстрой сортировке и вроде бы понял это, а также посмотрел видео об этом.
Вот проблема с домашним заданием:
Отсортируйте массив из 10 000 элементов с помощью алгоритма быстрой сортировки следующим образом:
a. Отсортируйте массив, используя pivot в качестве среднего элемента массива.
б. Отсортируйте массив, используя pivot в качестве медианы первого, последнего и среднего элементов массива.
c. Отсортируйте массив, используя pivot в качестве среднего элемента массива. Однако, когда размер любого подсписка уменьшается до менее чем 20, отсортируйте подсписк, используя сортировку по вставке.
d. Отсортируйте массив, используя pivot в качестве медианы первого, последнего и среднего элементов массива. Когда размер любого подсписка уменьшается до менее чем 20, отсортируйте подсписк, используя сортировку по вставке.
e. Вычислите и выведите время процессора для каждого из предыдущих четырех шагов.
Мне трудно понять — это будет одна целая функция, которая содержит эти четыре шага, или четыре разные функции, каждая из которых выполняет каждый шаг? Я понимаю, что это означает, выполнив шаг a при использовании pivot в качестве среднего элемента массива (допустим, у вас есть 10 элементов массива, а середина будет элементом # 4), но я не понимаю, что это значит «сортировать массив, используя pivot в качестве медианы первого, последнего и среднегоэлементы массива»
Мне нужно понимание внутренней работы быстрой сортировки и того, что требует от меня эта книга.
Комментарии:
1. 4 варианта алгоритма быстрой сортировки (от a до d) и сравнение таймингов (e).
2. «одна целая функция, которая содержит эти четыре шага, или четыре разные функции» , вероятно, 4 разные функции. Но ничто не мешает вам использовать вместо этого одну функцию с дополнительным параметром, который определяет, какой алгоритм следует использовать.
3. Медиана = середина. Учитывая 3 значения, отсортируйте их и выберите среднее.
4. Это может быть один исходный файл с операторами условной компиляции (#if … #elif … #else … #endif). Для b и d используйте два (если … / поменять местами …) для сортировки first, middle, last, чтобы медиана оказалась средним элементом. Можно использовать единую функцию, которая включает как сортировку по вставке, так и быструю сортировку. Средний элемент для pivot предлагает схему разделения Хоара . Средний элемент можно заменить на first или last и использовать в качестве pivot для Lomuto , но я не знаю, будет ли это принято.
5. Продолжая, вычисление процессорного времени для сортировки 10 000 элементов будет очень небольшим числом. Вам понадобится доступ к высокочастотному таймеру. Вы не упомянули, какой язык программирования используется или операционная система.