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

Преамбула

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

Задание

  1. Дан набор входных данных в количестве N значений. Модифицировать алгоритм пузырьковой сортировки таким образом, чтобы при любом наборе входных данных время их сортировки Tn было постоянным. Продемонстрировать разницу в работе исходного и модифицированныого алгоритма.

Дополнительная информация:

  1. Для получения текущего времени использовать функцию time(). Учитывать, что погрешность измерения времени данной функцией в Windows составляет 10-15 мс. В Linux погрешность отсутствует.
  2. Т.к. при решении задачи предполагается использование операционной системы общего назначения, допустима небольшая погрешность для Tn.
  3. Некоторые микропроцессоры оптимизируют свою работу с нарастающими или убывающими последовательностями. Поэтому, во избежание погрешностей, рекомендуется либо не хранить сортируемую последовательность в виде массива, либо использовать такие типы сортируемых данных, которые принудительно заблокируют оптимизационные возможности микропроцессора