Контрольные вопросы
-
Определение понятия массив
-
Объявление статических массивов
-
Поиск максимального или минимального элемента в массиве
-
Нахождение суммы и среднего арифметического для элементов массива
-
Переворот массива
-
Циклические сдвиги элементов массива вправо и влево
-
Вставка элемента в массив
-
Удаление элемента из массива
-
Написать реализацию одного из вариантов из таблицы 7.1
Лабораторная работа № 8. Сортировка массивов
Цели работы:
-
Познакомиться с понятием сортировки массивов.
-
Познакомиться с сортировкой массива посредством выбора.
-
Познакомиться с сортировкой обменом (метод пузырька).
-
Познакомиться с сортировкой массива методом вставки.
-
Познакомиться с операцией – вставка элемента в отсортированный массив.
-
Создать приложение, в котором наглядно выполняется сортировка одномерного массива различными методами, а также вставка элемента в отсортированный массив. Обеспечить выбор операции над массивом с помощью компонента MainMenu. Используя знакомые уже компоненты Memo или Edit осуществить возможность обмена данными между массивом и экраном.
Методы сортировки массивов
В программировании очень часто возникает задача размещения элементов в возрастающем или убывающем порядке. Представьте, насколько трудно было бы пользоваться словарем, если бы слова в нем не располагались в алфавитном порядке. Точно так же от порядка, в котором хранятся элементы в памяти компьютера, во многом зависит скорость и простота алгоритмов для их обработки.
Сортировка массива – процесс перестановки элементов массива с целью размещения элементов массива в определенном порядке.
Например, если сортируется массив А чисел по возрастанию, то после сортировки этого массива будет выполняться условие:
A[1] < A[2] < A[3] < …….< A[n]
Задача сортировки распространена в информационных системах и используется как предварительный этап задачи поиска, так как поиск в упорядоченном массиве производится намного быстрее, чем в неупорядоченном.
Существуют различные методы сортировки массивов.
Самыми простыми методами сортировки являются:
-
сортировка выбором;
-
сортировка обменом (метод пузырька);
-
сортировка вставкой (или включением).
-
Сортировка выбором
Алгоритм сортировки массива по возрастанию методом выбора можно описать так:
1. Среди всех элементов массива, начиная с первого, каким либо способом отыскивается минимальный элемент.
2. Найденный минимальный элемент помещается на место первого элемента.
3. Просматривается массив от второго элемента, находится минимальный среди оставшихся и помещается на место второго элемента.
4. И так далее до последнего элемента.
Рисунок 8.1 - Алгоритм сортировки по возрастанию методом выбора
Анализ описанных выше действий при сортировке выбором показывает, что для программной реализации этого метода сортировки потребуется два цикла for.
Во внешнем цикле должен изменяться номер изменяемого элемента от первого до предпоследнего. Этот цикл будет определять количество проходов по массиву.
Внутренний цикл должен обеспечить последовательное сравнение изменяемого элемента со всеми элементами, которые следуют в массиве за ним.
В теле внутреннего цикла производится сравнение элементов, индексы которых задаются параметрами внешнего и внутреннего цикла. Если при сравнении оказывается, что порядок следования элементов нарушен, то сравниваемые элементы меняются местами.
Схема алгоритма сортировки массива методом выбора показана на рисунке 8.1.
Исходными данными для алгоритма являются: сортируемый массив mas и количество элементов в этом массиве count.