Java, сортировка анализ. Heapsort, Quicksort1, Quicksort2, Mergesort, учитывая черный ящик

Question

Мне дали класс в Java под названием BlackBox. java. В этом классе есть четыре типа методов сортировки, и они называются sort1, sort2, sort3 и sort4. Дано, что у нас есть Mergesort, Heapsort, Quicksort с первым местом в массиве как pivot (не использует StdRandom.shuffle), и, наконец, у нас есть Quicksort, который берет середину первого и последнего элементов и использует это как pivot (также не использует StdRandom.shuffle).

Проблема в том, что мне нужно выяснить, какой метод сортировки (sort1, sort2, sort3, sort4) какой. Я уже посчитал время с вводом 500.000 целых чисел. Сначала я использовал случайный упорядоченный ввод, затем я использовал регулярную сортировку ввода и затем сортировку по входу в обратном порядке, и наконец я использовал действительно большой ввод с одинаковым целым числом, 3 везде ({3 3 3 3 3 ...}). Иногда я получаю переполнение стека, а иногда нет. У меня также было очень похожее время сортировки для всех них, я имею в виду очень похоже, что я не смог использовать его, чтобы сказать, какой алгоритм сортировки я использовал.

Как узнать, что за алгоритм? Какие методы я должен использовать?

PS. Я уже читал главу 1.4 в книге «Алгоритмы», написанную Седжвиком и Уэйном, и провел большой поиск по inte rnet. Может быть, я недостаточно понимаю главу 1.4. Итак, я прошу вас помочь мне с этой проблемой, если вы можете.

Кроме того, я не громко проверяю байт-код.

Answer 1

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

• Самый простой случай - быстрая сортировка, выбирающая первый элемент в качестве точки разворота; это уменьшается до квадратичного c времени, когда массив уже в порядке или в обратном порядке. Наилучший случай можно построить, убедившись, что ось всегда является медианой элементов в этом подмассиве.
• Следующий самый простой случай - быстрая сортировка с использованием середины массива в качестве оси; это также приводит к уменьшению квадратичного c времени для некоторых входных данных, но немного сложнее построить такие входные данные. Наилучший случай - это когда массив уже находится в порядке или в обратном порядке, так что средний элемент всегда является медианой.
• В худшем случае сортировка слиянием по-прежнему равна O (n log n), но тем не менее она медленнее на некоторых видах ввода. Стадия «слияния» выполняет наименьшее количество сравнений, когда все элементы в одном массиве меньше, чем все элементы в другом массиве, и наибольшее количество сравнений, когда два массива «чередуются» в максимально возможной степени.
• Heapsort по-прежнему равен O (n log n) в худшем случае, но также может быть быстрее или медленнее в зависимости от того, насколько далеко каждый элемент должен быть «просеян».

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

Answer 2

есть 3 основных различия между всеми этими алгоритмами:

1. сохранение порядка (стабильный / неустановленный)
2. порядок, в котором различные объекты сравниваются друг с другом (или сводной)
3. порядок, в котором меняются различные объекты

, чтобы проверить сохранение порядка, вам нужно отсортировать объекты с одним свойством сортировки и вторым, чтобы различать guish их, например:

class item {
  int sortid;
  string name;

  compareTo(item) -> return compare(this.sortid, item.sortid); note that name is not used
}

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

• слияние - стабильно
• куча - не стабильно
• быстро - не стабильно

отличается реализация быстрых сортировок сначала попытается переместить объекты меньше, чтобы повернуть влево и больше вправо, поэтому, если вы обнаружите, что ваши элементы сравниваются с первым элементом - это первая реализация сводки, я f с серединой - это вторая реализация быстрой сортировки

, для реализации которой вам нужно передать объекты с пользовательским сравнением, которое проверит, с каким элементом они сравниваются, и они знают, что можно использовать в качестве сводной, поэтому первое сравнение даст вам ответ, какой сводный элемент фактически используется каким методом сортировки

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