Визуализируйте вычислительную сложность двух алгоритмов сортировки, сортируйте пузырьки и объединяйте сортировку, которые сортируют элементы списка в порядке возрастания. Сортировка Bubble - это простой алгоритм сортировки, который неоднократно проходит по списку, сравнивает соседние пары элементов и меняет элементы, если они находятся в неправильном порядке. Сортировка слиянием является алгоритмом «разделения и завоевания», который использует простоту слияния отсортированных подсписков в новый отсортированный список.
В текущей папке сохраните следующий код в bubbleSort.m
.
Сохраните следующий код в mergeSort.m
.
Создайте следующий параметризованный класс теста, TestSort
, который сравнивает эффективность алгоритмов сортировки и слияния пузырьков. The len
свойство содержит количество элементов списка, которые необходимо протестировать.
Запустите тесты эффективности для всех тестовых элементов, которые соответствуют 'testBubbleSort'
метод и сохраните результаты в Baseline
массив. Результаты могут отличаться от показанных результатов.
Running TestSort
.......... .......... .......... .......... ..........
.......... .......... .......... .......... ..........
.......... .......... .......... .......... ..........
.......... .......... .......... .......... ..........
.......... .......... .......... .......... ..........
.......... .......... .....
Done TestSort
__________
Запустите тесты эффективности для всех элементов, которые соответствуют 'testMergeSort'
метод и сохраните результаты в Measurement
массив.
Running TestSort
.......... .......... .......... .......... ..........
.......... .......... .......... .......... ..........
.......... .......... .......... .......... ..........
.......... .......... .......... .......... ..........
Done TestSort
__________
Визуально сравните минимум MeasuredTime
столбец в Samples
таблица для каждой соответствующей пары Baseline
и Measurement
объекты.
На этом графике сравнения большинство точек данных синего цвета, потому что они находятся ниже затененной области подобия. Этот результат указывает на наилучшее решение сортировки слияния для большинства тестов. Однако для достаточно маленьких списков сортировка пузырей выполняется лучше, чем или сравнимо с сортировкой слиянием, как показано оранжевой и серой точками на графике.
В качестве сводных данных сравнения график сообщает об улучшении эффективности на 78% из-за сортировки слияния. Это значение является средним геометрическим процентом улучшения, соответствующим всем точкам данных. Если график сравнения содержит недопустимые точки данных, сводные данные сравнений не будет сгенерированы.
Вы можете нажать или навести на любую точку данных, чтобы просмотреть подробную информацию о сравнении результатов измерения времени.
Чтобы изучить эффективность алгоритма сортировки в худшем случае для различных длин списка, создайте сравнительный график на основе максимума времени измерения выборки.
Уменьшите SimilarityTolerance
на 0.01
при сравнении максимума времени измерения образца. Верните ComparisonPlot
объект в cp
чтобы можно было изменить его свойства позже.