5. Сортировка одномерного числового массива

Алиас: сортировка.

Цель работы

• освоение методов обработки массивов на примере сортировки массива;
• знакомство с алгоритмами сортировки;
• использование динамических массивов;
• инициализация массивов с помощью датчика случайных чисел;
• оценка быстродействия алгоритма.

Задание

Отсортировать числовой массив методами:

• метод сортировки выбором;
• методом пузырькового всплытия.

По окончании сортировки вывести:

• отсортированный массив;
• количество сделанных сравнений;
• перестановок элементов.

Сравнить быстродействие алгоритмов, которое определяется числом сравнений и перестановок, для исходного неотсортированного массива и для исходного массива, отсортированного в прямом и обратном порядке.

Исследовать зависимость быстродействия от размера массива. Возможность изменения длины массива реализуйте с помощью динамического массива, а для его инициализации используйте датчик случайных чисел. Результаты исследования выведите в виде таблицы (без рамок).

Ширина столбца: 16 символов.

предупреждение

Последний столбец пробелами не заполняется!

Пример вывода в консоли

В начале выводится результат работы для случайно сгенерированного динамического массива. Количество элементов в массиве: 5. Сортировка осуществляется по возрастанию и по убыванию. Сравнение быстродействия алгоритмов:

• сначала сортировка применяется к неотсортированному массиву (<название метода> (n));
• затем сортировка применяется к отсортированному массиву (<название метода> (o)).

к сведению

Алгоритмы сортировки массивов различаются по быстродействию и занимаемой памяти, причем эти характеристики зависят от упорядоченности сортируемого массива.

Затем генерируются массивы с количеством элементов 5, 50, 500. Сгенерированные массивы не выводить в консоль. Методы необходимо сравнивать на одинаковых массивах. Осуществлять сортировку по возрастанию на неотсортированном массиве.

Количество элементов: 5. Заданный массив: 10 1 2 3 4. Сортировка по возрастанию
Метод           Результат       Сравнений       Перестановок  
сравнений (n)   1 2 3 4 10      7               4
сравнений (о)   1 2 3 4 10      4               0
пузырек (n)     1 2 3 4 10      10              4
пузырек (о)     1 2 3 4 10      10              0

Количество элементов: 5. Заданный массив: 10 1 2 3 4. Сортировка по убыванию
Метод           Результат       Сравнений       Перестановок  
сравнений (n)   10 4 3 2 1      10              10
сравнений (о)   10 4 3 2 1      10              0
пузырек (n)     10 4 3 2 1      10              2
пузырек (о)     10 4 3 2 1      4               0

Метод: сравнений (n). Сортировка по возрастанию
N               Сравнений       Перестановок  
5               10              2
50              1225            43
500             124750          451

Метод: пузырек (n). Сортировка по возрастанию
N               Сравнений       Перестановок  
5               10              10
50              1159            586
500             43344           30914

Указания по выполнению работы

осторожно

Методы сортировки оформить в виде функций. В случае игнорирования данного требования, код будет отправлен на доработку.

При выполнении работы обратите внимание на следующие требования и рекомендации:

1. Необходимо использовать динамический массив.
2. Обнуления динамической памяти при ее выделении не происходит (см. какие конструкции для выделения памяти используются).
3. Автоматический контроль выхода индекса за границы массива не производится, поэтому программист должен следить за этим самостоятельно.
4. Перед выходом локального указателя из области его действия следует освобождать связанную с ним динамическую память.
   1. Для C освобождение памяти, выделенной посредством malloc, выполняется с помощью функции free.
   2. Для C++ Освобождение памяти, выделенной посредством new[], выполняется с помощью операции delete[].

Проверка задания

Подготовленная программа для решения задания проверяется вручную преподавателем (визуальный контроль).

Методический материал

1. Требования к отчету
2. Генератор случайного числа в диапазоне:
   1. Для программ на C
   2. Для программ на C++
3. Динамические массивы:
   1. Для программ на C
   2. Для программ на C++
4. Методы сортировки:
   1. Сортировка выбором
   2. Пузырьковая сортировка
5. Контрольные вопросы:
   1. Для потока на С
   2. Для потока на С++