Методы сортировки массивов с квадратичной трудоемкостью

  • ID: 29848 
  • 6 страниц
300 рубСкачать

гарантия низкой цены

L1.cpp

L1.exe

Отчет.docx

Фрагмент работы:

Лабораторная работа 1

Методы сортировки массивов с квадратичной трудоемкостью.

Цель работы: Освоить методы сортировки массивов с квадратичной трудоемкостью.

Для N = 100

Для N = 200

Для N = 300

Для N = 400

Для N = 500

Вывод:

В процессе выполнения лабораторной работы разработаны три метода сортировки массива с квадратичной трудоемкостью:

- методом прямого выбора;

- методом пузырька;

- шейкерная сортировка.

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

Начальная отсортированность массива на сортировку методом выбора никак не повлияла, результаты количества перемещений и сравнений в случях упорядоченного и не упорядоченного массива одинаковы. А в методах пузырька и шейкерной сортировок результаты трудоемкости такие:

- при сортировке массива в ту же сторону, что и начальная упорядоченность массива, количество перемещений равно нулю.