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