webprogr.ru Новости

Лабораторная работа «Поиск и сортировка»

Работа закрывает значительную часть двух разделов «Сортировка» и «Поиск и расстановка». 

Базовая часть:

• линейный поиск;

• линейный поиск с барьером как теоретический вариант;

• бинарный поиск;

• определение позиции вставки в упорядоченный массив.

Сортировки, обязательные к реализации:

• пузырьковая;

• выбором;

• вставками;

• слиянием;

• быстрая.

Готовый Array.prototype.sort() разрешается применять только как контроль результата, но не как решение.

Эксперимент: для каждого алгоритма использовать четыре типа данных:

1. случайный массив;

2. уже отсортированный;

3. отсортированный в обратном порядке;

4. массив с большим числом повторов.

Размеры, например:

100, 500, 1000, 5000, а для квадратичных методов слишком большие размеры можно ограничить.

Для каждого эксперимента фиксируются:

• размер n;

• время;

• количество сравнений;

• количество обменов;

• результат проверки правильности.

Студент должен получить экспериментальное подтверждение различий между O(n²) и O(n log n).